Rompecabezas de la matemáticas: de 10 dígitos de las cadenas de generaciones

Question

Había una pregunta en una competencia de matemáticas a la que asistí el año pasado. Al final de la competencia, me di cuenta de que mi respuesta fue incorrecta de la pregunta de abajo y nunca he sido capaz de averiguar cómo resolverlo.

Aquí está la pregunta:

Se le pide a generar de 10 dígitos de cadenas utilizando los dígitos de 0 a 9 una vez cada uno. Cualquiera de los cuatro dígitos de la subcadena se utiliza en una cadena que no puede ser utilizado de nuevo.

¿Cuál es el mayor número de cadenas de caracteres que puede generar el uso de estas reglas? (y necesito la lista de ellos)

Ejemplo:

Si utiliza una cadena 0243697518 en su lista, usted puede no generar cadenas contienen 0243, 2436, 4369, 3697, 6975, 9751 y 7518

Para resolver el problema, he escrito un programa de c++, simplemente analizar todos los permutación de "0123456789" y añadirlos a una lista de solución si 4 dígitos sub-cadenas de que el código no ha sido usado antes. Pero el problema de mi algoritmo es que el tamaño de la lista de solución varía dependiendo de su punto de partida que se agrega a la lista en primer lugar. Si empiezo a añadir en la lista de "0123456789", lista termina con 504 entradas que no es el máximo preguntó. Realmente me pregunto cómo resolver esta cuestión, cualquier ayuda muy apreciada. Estoy abierto a escuchar su solución matemática o de cualquier algoritmo de sugerencias para generar la lista de pedido.

Histograma de random como sugiere Pedro (min: 575, max: 606):

Por encima de algoritmo intenta generar la lista de pedido mediante el escaneo de todos los posibles de 10 dígitos de cadenas de caracteres en una secuencia aleatoria. Histograma generado más de 100 mil ensayos. Porque todos los posibles 10 cadenas de dígitos necesarios para ser analizados para cada una de las iteraciones son de 10! = 3,6 millones, cada una de las iteraciones tarda 10 segundos en mi pc para completar. Yo podría intentar optimizar mi algoritmo más si yo creía que no había realmente ninguna determinista solución para la cuestión.

Answer 1

La secuencia de Bruijn da aproximadamente 1428 posibilidades (10000/7 más o menos uno o dos debido al redondeo): cambio de una ventana de tamaño 10, a través de ella, cada vez que cambio de 3 posiciones.

Editar (lo siento, yo también perdió la parte que desea permutaciones). Esto podría traer un poco más cerca de lo que usted necesita: "Universal ciclos de k-subconjuntos de k y permutaciones" por B. W. Jackson, y también buscar nuevos papeles y libros citar este documento (por ejemplo, en Google scholar). Mediante la construcción de un Euleriano pie en un gráfico puede generar un ciclo que contiene cada parcial 4-permutación exactamente una vez, algo que se llama un ciclo universal (ucycle) de parcial permutaciones.

Answer 2

En lugar de iterar entre números de 10 dígitos, hacer una lista de todas las posibles 4 dígitos (que se $10*9*8*7=5040$ y combinar 7 4 dígitos a la vez para obtener números de 10 dígitos. Se trata de una programación dinámica de pregunta y usted tendrá que dar marcha atrás para obtener ya se utiliza de 4 dígitos en números de 10 dígitos que requieren la mayoría de ellos. Con este enfoque, el máximo posible de 10 dígitos cadenas deben ser $(10*9*8*7)/7=720$.

Answer 3

No tengo una solución, pero aquí están algunas ideas sobre el problema. Podemos mirar el $(m,n)$ de encontrar el máximo número posible de las cadenas de $m$ símbolos sin cadenas de longitud $n$ utiliza más de una vez en el conjunto de cadenas. Se puede construir un gráfico de $G$ cuyos vértices $V$ $n$dígitos cadenas. Vamos a poner una arista entre dos vértices $v$ $v'$ si las cadenas de la superposición de la siguiente manera

$$v = s_1 s_2 \ldots s_n, \quad v' = s_2 \ldots s_n s_{n+1}$$

donde $s_1 \neq s_{n+1}$. Nos conectamos cada vértice $v$ $m-n$otros vértices. También cada vértice ha $m-n$ bordes que conducen a ella. En general

$$|V| = n!\binom{m}{n} = \frac{m!}{(m-n)!},\quad |E| = (m-n)|V| = \frac{m!}{(m-n-1)!}$$

Podemos representar cada una de las $m$-cadena de dígitos por una trayectoria en $G$ de la longitud de la $m-n$, conteniendo $m-n+1$ vértices. Tenemos que encontrar el número máximo de vértices disjuntos rutas en $G$. Uno podría tener un máximo teórico de

$$\frac{m!}{(m-n+1)!}$$

esos caminos se si todos los vértices son utilizados. En su caso, de $m = 10$, $n = 4$ tienes 720 posibles rutas de acceso y de el problema que usted sabe que usted puede encontrar muchos caminos. Esto corresponde a la búsqueda de un vértice de la cubierta de $G$ consta de rutas de vértice longitud 7. Si alguien sabe de un algoritmo para encontrar una cubierta, a continuación, se puede aplicar a este problema. Esto no es siempre el caso. Para $m = 3$ $n = 2$ que usted esperaría $6/2 = 3$ de esos caminos, pero el gráfico de $G$ se compone de 2 discontinuo dirigida 3-ciclos.

Claramente, el gráfico de $G$ tiene que permanecen invariantes por cualquier permutación de los dígitos, de forma que se puede establecer fácilmente una de las rutas de acceso de la cubierta como se $0123\to 1234 \to \cdots \to 6789$.

Otra cosa a tener en cuenta es que, si podemos encontrar un ciclo Hamiltoniano en el grafo podemos eliminar todos los $m-n+1$-th borde para obtener una máxima cobertura en caso de que exista. Por desgracia no tengo un algoritmo para la búsqueda de ciclos Hamiltonianos en un grafo dirigido, pero alguien más podría.