cadena de enteros rompecabezas

Question

Pido disculpas por no tener los conocimientos matemáticos para formular esta pregunta de una manera más formal. Estoy buscando crear una cadena de 796 letras (o enteros) con ciertas propiedades.

Básicamente, la cadena es una variación de una secuencia De Bruijn B (12,4), excepto que el orden y la repetición dentro de cada subsecuencia n de longitud se descartan. es decir, ABBB BABA BBBA son equivalentes a {AB}. En otras palabras, la propiedad principal de la cadena consiste en mirar grupos consecutivos de 4 letras dentro de la cadena más grande (es decir, la 1ª a la 4ª letras, la 2ª a la 5ª letras, la 3ª a la 6ª letras, etc.) Y luego producir el conjunto de letras que componen cada grupo (repeticiones y el orden descartadas)

Por ejemplo, en la cadena de 9 letras:

ABBACEBCD

los primeros grupos de 4 letras es: ABBA, que se compone del conjunto {AB} el segundo grupo es: BBAC, que se compone de s et {ABC} El tercer grupo es: BACE, que se compone del conjunto {ABCE} etc.

El objetivo es que cada combinación de 1-4 cartas de un conjunto de N cartas a ser representada por la Conjuntos resultantes de 1 a 4 letras de los grupos de 4 elementos una vez y solo una vez en la cadena original.

Por ejemplo, si hay un conjunto de 5 cartas {A, B, C, D, E} que se utiliza Entonces las posibles combinaciones de letras 1-4 son: A, B, C, D, E, AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE, ABCD, ABCE, ABDE, ACDE , BCDE

Aquí hay un ejemplo de trabajo que usa un conjunto de 5 letras {A, B, C, D, E}.

DDDDECBBBBAECCCCDAEEE EBDAAAACBDDB

El primero a 4to elementos forman el conjunto: D El segundo a través de elementos de 5to integran el conjunto: DE El tercero a través de elementos de 6º integran el conjunto: CDE El cuarto hasta el 7 de elementos forman la conjunto: BCDE el quinto a través de elementos de 8º forman el conjunto: BCE el sexto a través de elementos 9º forman el conjunto: BC el séptimo a través de elementos 10º forman el conjunto: B etc.

* Estoy esperando encontrar un ejemplo funcional de una cadena que utiliza 12 letras diferentes (un total de 793 grupos de 4 letras dentro de una cadena de 796 letras) comenzando (y si es posible terminando) con 4 de la misma letra. *

Aquí es una solución de trabajo de 7 letras:

AAAABCDBEAAACDECFAAADBFBACEAGAADEFBAGACDFBGCCCCDGEAFAGCBEEECGFFBFEGGGGFDEEEEFCBBBBGDCFFFFDAGBEGDDDDBE

Answer 1

problema fresca.Sólo un proyecto/pseudo algo:

dim STR-A as string = getall(ABCDEFGHIJKL) 
//custom function to generate concat list of all 793 4-char combos. 
//should be listed side-by-side to form 3172 character-long string. 
//different ordering may ultimately produce different results. 
//brute-forcing all orders of combos is too much work (793! is a big #). 
//need to determine how to find optimal ordering, for this particular 
//approach below. 
dim STR-B as string = "" // to hold the string you're searching for 
dim STR-C as string = "" // to hold the sub-string you are searching in 
dim STR-A-NEW as string = "" //variable to hold your new string 
dim MATCH as boolean = false //variable to hold matching status 

while len(STR-A) > 0 
//check each character in STR-A, which will be shorted by 1 char on each 
//pass. 
    MATCH = false 
    STR-B = left(STR-A, 4) 
    STR-B = reduce(STR-B) 
    //reduce(str) is a custom re-usable function to sort & remove duplicates 

    for i as integer = 1 to len((STR-A) - 1) 
    STR-C = substr(STR-A, i, 4) 
    //gives you the 4-character sequence beginning at position i 
    STR-C = reduce(STR-C) 
    IF STR-B = STR-C Then 
     MATCH = true 
     exit for 
     //as long as there is even one match, you can throw-away the first 
     //letter 
    END IF 
    i = i+1 
    next 


    IF match = false then 
    //if you didn't find a match, then the first letter should be saved 
    STR-A-NEW += LEFT(STR-B, 1) 
    END IF 

    MATCH = false //re-init MATCH 
    STR-A = RIGHT(STR-A, LEN(STR-A) - 1) //re-init STR_A 
wend 

De todos modos - que podría haber problemas en este, y que había necesidad de escribir otra función para analizar la cadena de resultado (STR-A-NUEVO) para demostrar que se trata de una respuesta viable ...

Answer 2

Tenga en cuenta que para intentar una búsqueda exhaustiva (la respuesta en VB es intentar una versión ingenua de eso) primero tendrá que resolver el problema de generar todas las expansiones posibles manteniendo el orden lexicográfico. ¡Solo ABC, se expande a todas las permeabilidades de AABC, más todas las perms de ABBC, más todas las perms de ABCC que son 3 * 4! en lugar de solo AABC. Si concatenas AABC y AABD, ¡cubriría solo 4 de 4! permanentes de AABC e incluso eso por accidente. Solo esta expansión te brindará una complejidad exponencial: final del juego. Además, deberá mantener la asociación entre todas las explicaciones y el conjunto (el conjunto se convierte en una etiqueta).

Su mejor opción es utilizar uno de los contructors eficientes conocidos de De Bruijn y tratar de ver si puede poner su equivalencia de set allí. Salida

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.674&rep=rep1&type=pdf

y

http://www.dim.uchile.cl/~emoreno/publicaciones/FINALES/copyrighted/IPL05-De_Bruijn_sequences_and_De_Bruijn_graphs_for_a_general_language.pdf

para empezar.

Si conoce los gráficos, otra opción viable es comenzar con el gráfico de De Bruijn y formular su equivalencia de set como una reescritura de gráfico. El segundo trabajo presenta la partición gráfica de De Bruijn.

Por cierto, intente con la respuesta VB solo para A, B, AB (al menos la expansión es pequeña) - creará AABBAB y construirá ABBA o ABBAB (o arrojará un lenguaje decente), ambos incorrectos. Incluso puede probar que siempre se perderá con las primeras expansiones léxicas (eso es lo que AAB, AAAB, etc.) simplemente examinando los primeros 2 pases (siempre fallará la 2ª A para NxA porque (N-1) xA + B está en el cadena (primera expansión de {AB}).

Ah, y si pudiéramos establecer cuántas de cada letras debe tener una solución óptima (no mires a B (5,2) es demasiado fácil y regular :-) un servidor aleatorio sería factible: generará candidatos con características comprobables (como AAAA, BBBB ... están presentes y no se tocan y tiene n1 As, n2 Bs ...) y una disposición aleatoria y luego probará si son soluciones (verificar es mucho más rápido que la búsqueda exhaustiva en este caso).

Answer 3

He estado pensando en esto y estoy esbozando una solución.

Vamos a llamar a una cadena de cuatro símbolos de una palabray escribiremos S (w) para denotar el conjunto de símbolos de palabra w .

Cada palabra tiene ABCD "de continuación" palabras Bcde donde a, ..., e son todos los símbolos.

Vamos succ (w) ser el conjunto de seguimiento de palabras v para w tal que S (w)! = S (v).succ (w) es el conjunto de palabras sucesoras que pueden seguir desde el primer símbolo en w si w está en una solución.

Para cada conjunto no vacío de símbolos s de cardinalidad como máximo cuatro, dejar palabras (s) el conjunto de palabras w tal que S (w) = s. Cualquier solución debe contener exactamente una palabra en palabras (s) para cada uno de tales conjuntos s.

Ahora podemos hacer una búsqueda razonable. La idea básica es la siguiente: supongamos que estamos explorando una ruta de búsqueda que finaliza con la palabra w. La palabra siguiente debe ser una palabra no excluida en succ (w). Se excluye una palabra v si la ruta de búsqueda contiene alguna palabra w tal que v en las palabras (S (w)).

Puede ser un poco más astuto: si hacemos un seguimiento de los posibles palabras "precedentes" a un conjunto s (es decir, palabras w con un sucesor v tal que v en palabras (s)) y llegar a un punto donde se excluye cada predecesor de s, entonces sabemos que hemos llegado a un callejón sin salida, ya que nunca podremos obtener s desde cualquier extensión de la ruta de búsqueda actual.

Código a seguir después del fin de semana, con un poco de suerte ...

Answer 4

Aquí es mi propuesta. Admito de antemano que esto es un rendimiento y un problema de memoria.

Esto puede ser exagerado, pero tiene una clase Lo llamaremos UniqueCombination Esto contendrá una combinación única de 1-4 caracteres reducidos del conjunto de entrada (es decir, A, AB, ABC, ...) Esto también contendrá una lista de combinación posible (AB {AABB, ABAB, BBAA, ...}) Esto necesitará un método que determine si cualquier combinación posible se superpone a cualquier combinación posible de otra UniqueCombination por tres caracteres. También necesita una anulación que también toma una cadena.

Luego comenzamos con la cadena "AAAA" luego encontramos todas las UniqueCombinations que se superponen a esta cadena. Luego, descubrimos cuántas combinaciones únicas coinciden esas coincidencias posibles. (Podríamos ser inteligentes en este punto en una tienda de este número.) Luego seleccionaremos el que tenga el menor número de superposiciones mayor que 0. Use primero los que tengan la menor cantidad posible de coincidencias.

Luego encontramos una combinación específica para el UniqueCombination elegido y lo agregamos a la cadena final. Elimine esta UniqueCombination de la lista, luego, a medida que encontramos superposiciones para la cadena actual. enjuague y repita. (Podríamos ser inteligentes y en ejecuciones posteriores mientras buscamos superposiciones podríamos eliminar cualquiera de las combinaciones no reducidas que están contenidas en la cadena final).

Bueno, ese es mi plan. Trabajaré en el código este fin de semana. Por supuesto, esto no garantiza que los 4 caracteres finales sean 4 de la misma letra (en realidad podría tratar de evitar eso, pero también investigaré eso).

Answer 5

Si hay una solución no exponencial en absoluto puede necesitar formularse en términos de un "crecimiento" recursivo a partir de un problema con un tamaño más pequeño i.e para construir B (N, k) desde B (N-1, k-1) o desde B (N-1, k) o desde B (N, k-1).

Construcción sistemática para B (5,2) - un paso en el momento :-) Se complicará más tarde [la tarjeta significa cardinalidad, {AB} tiene tarjeta = 2, también los llamaré 2 -s, 3-s, etc.] Nota: 2-s y 3-s serán k-1 y k serán posteriores (espero).

1. Inicial. Comience con k-1 resultado e inyectar símbolos para singletons (expansión único de intersección vacío):
   • ABCDE -> AABBCCDDEE
2. marca tarjeta utilizada = 2 juegos: AB, BC, CD, DE
3. Reescritura. Form card = 3 sets para inyectar símbolos en la tarjeta marcada = 2. 1ª posibles incendios de expansión lexicográficas (pueden tener que dar marcha atrás para k> 2)
   • que está bien usar ya marcó 2-s, ya que va todo reemplazados
   • pero puede tener que hacer un paso de comprobación para una mayor k
   • AB-> ACB, BC-> BCD, CD-> CED, DE-> DAE ==> AACBBDCCEDDAEEB marca
4. /verificar 2s usadas
   • normalmente mantienen marcado/desmarcado durante el construcción sino también mantener mantener antigua lista marca
   • marcando/desmarcando puede ser caro si hay marcha atrás en el # 3
   • no utilizado: AB, BE
5. Para mayor k se pueden necesitar varias reescritura recursiva pases
   • posiblemente la partición de nuevos conjuntos en clases
6. Finalizar: sin usar 2-s debe superponerse alrededor del borde (por eso es cíclico) ABE - B puede ir al principio o y: AACBBDCCEDDAEEB

Nota: un paso de B (N-1, k) a B (N, K) pueden necesitar la inyección de pseudo-signletons, como duplicar o Un trippling

B (5,2) -> B (5,3) - B (5,4)

1. inicial. mismo: - ABCDE -> AAACBBBDCCCEDDDAEEEB
2. sin uso de marcado 3-sets ya que todos van a ser chenged
3. Reescritura.
   1. elegir posiciones de inserción sistemáticas
      • AAA_CBBB_DCCC_EDDD_AEEE_B
   2. marca de los 2-es liberado por esto: AC, AD, BD, BE, CE
   3. utilización marcó 2-s para decidir inserta - símbolos totice total regularidad:
      • AxCB D -> ADCB
      • BxDC E -> BEDC
      • CxED A -> CAED
      • DxAE B => DBAE
      • EXBA C -> ECBA
4. Compruebe que 3-s son todos utilizados (símbolos insertados marcados sólo para diversión)
   • AAA [D] CBBB [E] DCCC [A] eddd [B] AEEE [C] B

Nota: la elección sistemática si el punto de inserción inserciones de forma determinista dictadas (solamente AD puede encajar primero, CA crearía duplicado 2-conjunto (AAC, ACC))

Nota: No va a ser tan agradable para B (6 , 2) y B (6,3) ya que el número de 2-s excederá 2 veces el no de 1-s. Esto es importante ya que los 2-s se sientan naturalmente en los lados de 1-s como CBBBE y el problema es cómo colocarlos cuando se quede sin 1-s.

• B (5,3) es tan simétrica que simplemente repetir # 1 produce B (5,4):
  • AAAADCBBBBEDCCCCAEDDDDBAEEEECB