Subsecuencias de Wirth

propuesto por josejuan

Encontrar todas las cadenas de N caracteres "A", "B" o "C" tales que no contengan dos subsecuencias consecutivas.

Enunciado
Encontrar todas las cadenas de N caracteres "A", "B" o "C" tales que no contengan dos subsecuencias consecutivas.

Es decir:

1. las cadenas de salida deben tener longitud N.

2. los únicos caracteres posibles son "A", "B" o "C".

3. en las cadenas resultantes, no debe poderse encontrar dos subsecuencias consecutivas.

4. deben encontrarse todas las cadenas posibles que cumplan las condiciones (para un N dado).

Por ejemplo, para N=3 es válida la cadena "ABA" porque aunque la subsecuencia "A" se repite dos veces, no está de forma consecutiva.

Para N=4, no sería válida la cadena "ABAB" porque la subsecuencia "AB" se repite de forma consecutiva.

Por ejemplo, para N=1..6 todas las cadenas en cada caso son (salvo error, claro):

A,B,C

AB,AC,BA,BC,CA,CB

ABA,ABC,ACA,ACB,BAB,BAC,BCA,BCB,CAB,CAC,CBA,CBC

ABAC,ABCA,ABCB,ACAB,ACBA,ACBC,BABC,BACA,BACB,BCAB,BCAC
BCBA,CABA,CABC,CACB,CBAB,CBAC,CBCA

ABACA,ABACB,ABCAB,ABCAC,ABCBA,ACABA,ACABC,ACBAB,ACBAC
ACBCA,BABCA,BABCB,BACAB,BACBA,BACBC,BCABA,BCABC,BCACB
BCBAB,BCBAC,CABAC,CABCA,CABCB,CACBA,CACBC,CBABC,CBACA
CBACB,CBCAB,CBCAC

ABACAB,ABACBA,ABACBC,ABCABA,ABCACB,ABCBAB,ABCBAC,ACABAC
ACABCA,ACABCB,ACBABC,ACBACA,ACBCAB,ACBCAC,BABCAB,BABCAC
BABCBA,BACABA,BACABC,BACBAB,BACBCA,BCABAC,BCABCB,BCACBA
BCACBC,BCBABC,BCBACA,BCBACB,CABACA,CABACB,CABCAC,CABCBA
CACBAB,CACBAC,CACBCA,CBABCA,CBABCB,CBACAB,CBACBC,CBCABA
CBCABC,CBCACB

A modo de verificación (salvo que el error esté en mi lista, claro :P ) dejo las longitudes de los conjuntos Wirth con longitud de secuencia igual o menor a 40:

Length( Wirth( 0 ) ) = 1
Length( Wirth( 1 ) ) = 3
Length( Wirth( 2 ) ) = 6
Length( Wirth( 3 ) ) = 12
Length( Wirth( 4 ) ) = 18
Length( Wirth( 5 ) ) = 30
Length( Wirth( 6 ) ) = 42
Length( Wirth( 7 ) ) = 60
Length( Wirth( 8 ) ) = 78
Length( Wirth( 9 ) ) = 108
Length( Wirth( 10 ) ) = 144
Length( Wirth( 11 ) ) = 204
Length( Wirth( 12 ) ) = 264
Length( Wirth( 13 ) ) = 342
Length( Wirth( 14 ) ) = 456
Length( Wirth( 15 ) ) = 618
Length( Wirth( 16 ) ) = 798
Length( Wirth( 17 ) ) = 1044
Length( Wirth( 18 ) ) = 1392
Length( Wirth( 19 ) ) = 1830
Length( Wirth( 20 ) ) = 2388
Length( Wirth( 21 ) ) = 3180
Length( Wirth( 22 ) ) = 4146
Length( Wirth( 23 ) ) = 5418
Length( Wirth( 24 ) ) = 7032
Length( Wirth( 25 ) ) = 9198
Length( Wirth( 26 ) ) = 11892
Length( Wirth( 27 ) ) = 15486
Length( Wirth( 28 ) ) = 20220
Length( Wirth( 29 ) ) = 26424
Length( Wirth( 30 ) ) = 34422
Length( Wirth( 31 ) ) = 44862
Length( Wirth( 32 ) ) = 58446
Length( Wirth( 33 ) ) = 76122
Length( Wirth( 34 ) ) = 99276
Length( Wirth( 35 ) ) = 129516
Length( Wirth( 36 ) ) = 168546
Length( Wirth( 37 ) ) = 219516
Length( Wirth( 38 ) ) = 285750
Length( Wirth( 39 ) ) = 372204
Length( Wirth( 40 ) ) = 484446

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

8 Soluciones

Dar mi solución

0votos
Subsecuencias de Wirth en C
por

josejuan

hace 6 años

A veces ser bruto tiene sus ventajas. La versión de C mejora a Haskell en 125 veces más rápido. Cierto que Haskell está paralelizado (y con suficientes procesadores lo mejoraría), pero un buen ejemplo de que a veces hacer el bruto merece la pena XD XD XD

0votos
Subsecuencias de Wirth en PHP
por

Pepe

hace 6 años

Primer intento en PHP para este bonito problema. El lenguaje no se presta mucho a la recursividad, pero ahí va en forma recursiva. Hice solo un par de mejoras para eliminar el uso de las funciones lentas "strlen" y "substr", así como cachear los resultados ya calculados para acelerar la recursividad. Con esto tengo hasta N=30 en unos 10 segundos, y hasta N=40 en unos 3 min. Muy mejorable, pero por lo menos no tan cutre como la solución que hice en Ruby :-)

0votos
Subsecuencias de Wirth en Haskell
por

josejuan

hace 6 años

Una propiedad interesante de las secuencias Wirth es que el conjunto n-wirth se puede generar a partir del (n-1)-wirth tan sólo añadiendo un carácter a cada elemento (A, B o C en el enunciado) y ver si el prefijo de 1, 2, 3, ... caracteres queda repetido al principio del nuevo elemento generado. El conjunto 0-wirth es la cadena vacía, claro.

0votos
Subsecuencias de Wirth en Python
por

drabor

hace 6 años

Ahora sí, es el mismo planteamiento que el anterior solo que más corto, claro y rápido (Para n = 11 pasa de 2.68 a 0.12 segundos). Quería dejar esta versión bien hecha antes de buscar otra solución como dice josejuan sin usar permutaciones.

Dar mi solución