4 votos

Combinaciones de 2 dígitos

Puedo contar el número de combinaciones de 2 dígitos: cada dígito tiene 10 posibilidades, por lo que eso da 10*10 = 100 combinaciones.

Pero, ¿qué pasa si escribimos las combinaciones en una larga cadena como esta:

112131

Esta cadena tiene 6 de largo, pero nos da 5 combinaciones: 11, 12, 13, 21 y 31

¿Cómo puedo calcular la cadena más corta que me dé las 100 combinaciones? ¿De qué longitud necesitará ser para todas las combinaciones de n dígitos? ¿Cómo puedo generar la secuencia?

Recuerdo haber escuchado sobre esto en algún lugar, pero lo olvidé. Si pudiera obtener solo el nombre de cómo se llama.

3voto

jwarzech Puntos 2769

Probablemente estás pensando en secuencias de De Bruijn. Estas son a menudo generadas para un "alfabeto" binario, pero pueden formarse para cualquier tamaño de alfabeto $k$.

Con wraparound se puede obtener la longitud mínima de la secuencia $k^n$ para todas las subsecuencias en un alfabeto de tamaño $k$.

Si no se permite el wraparound, entonces la secuencia tiene que ser "rellenada" con los primeros $n-1$ caracteres repetidos al final, para una longitud total de $k^n + n - 1$.

El Servidor de Objetos Combinatorios tiene un generador de secuencias de De Bruijn (entre otras cosas), y para $n=2, k=10$ como en la pregunta, produjo esta secuencia (la menor lexicográficamente):

0010203040506070809112131415161718192232425262728293343536373839445464748495565758596676869778798899

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X