Un "esquema de rima" es una cadena de letras apara z, de modo que las primeras apariciones de los caracteres están en orden ascendente (sin espacios), comenzando desde a. Por ejemplo (con las primeras ocurrencias marcadas):

abccdbebdcfa
^^^ ^ ^   ^

La cantidad de esquemas de rima de longitud Nviene dada por los números de Bell B(N) . ( OEIS A000110 )

El reto

Su tarea es implementar una enumeración de estos esquemas de rima, es decir, un mapeo biyectivo de enteros a esquemas de rima. Te dan un número entero positivo N <= 26, así como un número entero no negativo 0 <= i < B(N). Alternativamente, puede usar el rango 1 <= i <= B(N). Debe generar un esquema de rima de longitud N, de modo que cada uno iproduzca una cadena diferente.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Puede usar letras minúsculas o mayúsculas (consistentemente).

Su código debe ser capaz de manejar cualquier entrada válida en un tiempo razonable (por ejemplo, no más de unas pocas horas para el N = 26peor de los casos i). Esto debería permitir soluciones que se escalen exponencialmente con N(para bases pequeñas), incluso en lenguajes lentos pero que prohíban soluciones que se escalen linealmente con i(es decir B(N)). En particular, eso significa que no puede simplemente iterar a través de todos los esquemas de longitud de rima válidos Nhasta que haya descartado los iesquemas.

Se aplican reglas estándar de código de golf .

Ejemplos

La asignación exacta de los iesquemas to (es decir, el orden de los esquemas para un determinado N) depende de usted. Pero supongamos que eligió el orden lexicográfico, su solución debe corresponder a la siguiente tabla (con una -entrada no válida):

N\i 1    2    3    4    5    6    7    8    9    10   11   12   13   14   15
1   a    -    -    -    -    -    -    -    -    -    -    -    -    -    -
2   aa   ab   -    -    -    -    -    -    -    -    -    -    -    -    -
3   aaa  aab  aba  abb  abc  -    -    -    -    -    -    -    -    -    -
4   aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd

Aquí hay un breve script de CJam que genera todos los esquemas de rima válidos para cualquier longitud dada (pero no intentes más de 10 o esperarás un tiempo).

Desafíos relacionados

• Traducir un programa Glypho
• Comprueba si las palabras son isomorfos

CJam, 68 66 bytes

r~:W)1a*{__(;\);_,,.*.+}W(*r~{X@\=_2$\/:CX<!{X:C):X;}&C*-C'a+o}W*;

Pruébalo en línea.

Este es mi primer programa CJam. Comenzó como un puerto de mi solución Perl e inicialmente tenía más de 130 bytes de longitud. Más sugerencias de golf son bienvenidas.

Al igual que con mi programa Perl, consta de dos partes.

Part 1:
r~:W                                         | Read the first input (n) and store it in W
    )1a*                                     | Create an array of n+1 1s
        {              }W(*                  | Repeat n-1 times:
         __                                  | Duplicate array twice
           (;\);                             | Remove first element of 1st array. Swap
                                             | arrays. Remove last element of 2nd array
                _,,                          | Duplicate array. Count items. Create range
                   .*.+                      | Multiply arrays. Add 1st array to result

Part 2:
r~                                           | Read the second input (i)
   {                                  }W*    | Repeat n times:
    X@                                       | Push y (initially 1). Bring item 2 (last array) to top
     \=                                      | Swap top two items. Pop array[y] (v)
       _2$                                   | Duplicate v. Copy item 2 (i) to top
          \/:CX                              | Swap i & v. i/v. Store in C (c). Push y
               <!{       }&                  | If !(i/v < c):
                  X:C):X;                    | c = y. ++y (store in X)
                           C*-C'a+o          | i -= c * v. Push y. Push "a". Add c. Print
                                         ;   | Discard top item (integer 0)

Para depurar las matrices creadas por la Parte 1 add ]_`o~entre las partes 1 y 2. Si n es 5, las matrices se vería así: [[1 1 1 1 1 1] [1 2 3 4 5] [2 5 10 17] [5 15 37] [15 52]]. Los 0 índices de cada matriz no se usan, simplemente lo hacen más fácil al no tener que calcular las compensaciones. Las matrices se calculan así:

[2 5 10 17] [2 5 10 17] [2 5 10 17]        | Duplicate twice
[2 5 10 17] [2 5 10 17] [5 10 17]          | Discard first item of array
[2 5 10 17] [5 10 17] [2 5 10 17]          | Swap last two arrays
[2 5 10 17] [5 10 17] [2 5 10]             | Discard last item of array
[2 5 10 17] [5 10 17] [2 5 10] [2 5 10]    | Duplicate array
[2 5 10 17] [5 10 17] [2 5 10] 3           | Count items in array
[2 5 10 17] [5 10 17] [2 5 10] [0 1 2]     | Integer to range 0 - n-1
[2 5 10 17] [5 10 17] [0 5 20]             | Multiply arrays [2*0 5*1 10*2]
[2 5 10 17] [5 15 37]                      | Add arrays [5+0 10+5 17+20]

Mantiene una copia de la matriz anterior mientras calcula la siguiente. Las matrices se leen y se descartan en orden inverso en la Parte 2.

Pitón 2, 153

u=[1]*999;i=60;exec"u[i]=i%30*u[i-30]+u[i-29];i+=1;"*900
def x(l,n,a=0):m=u[30*l+a];c=n>=a*m;return'.'*l and chr(65+min(n/m,a))+x(l-1,[n%m,n-m*a][c],a+c)

Utiliza el orden alfabético y la indexación basada en 0.

Deje que ldenote la longitud de un sufijo de las letras y adenote el número de letras distintas que se usaron en la parte anterior. Entonces, una función p(l,a)que calcula la cantidad de formas de seleccionar las letras restantes podría ser de 40 bytes:

p=lambda l,a:l<1or a*p(l-1,a)+p(l-1,a+1)

Sin embargo, esto es demasiado lento para el desafío, por lo que los valores necesarios se calculan previamente y se almacenan en la umatriz. En cada etapa del cálculo, si la siguiente letra es una de las aya utilizadas, n = k * p (l - 1, a) + n ' donde k es la letra del alfabeto indexada en 0 y n' es El valor de npara la siguiente llamada de función, que contiene la información sobre las letras restantes. Si se usa una nueva letra, entonces n = a * p (l - 1, a) + n ' .

Haskell (GHC 7.10), 150 bytes

s=(1,\_->[]):s
k!((y,b):l@((x,a):_))|let h i|i<x=k:a i|(p,q)<-divMod(i-x)y=p:b q=(x+k*y,h):(k+1)!l
n#i=(['a'..]!!).fromEnum<$>snd(iterate(0!)s!!n!!0)i

El operador n # icalcula el iesquema de longitud de la rima th (indexado a cero) n. Se ejecuta en operaciones O (n²) (entero grande), aprovechando las listas infinitas perezosas de Haskell para la memorización automática. Ejecuciones de muestra:

*Main> 26 # 0
"abcdefghijklmnopqrstuvwxyz"
*Main> 26 # 1
"abcdefghijklmnopqrstuvwxya"
*Main> 26 # 2
"abcdefghijklmnopqrstuvwxyb"
*Main> 26 # 49631246523618756271
"aaaaaaaaaaaaaaaaaaaaaaaabb"
*Main> 26 # 49631246523618756272
"aaaaaaaaaaaaaaaaaaaaaaaaab"
*Main> 26 # 49631246523618756273
"aaaaaaaaaaaaaaaaaaaaaaaaaa"
*Main> [1 # i | i <- [0..0]]
["a"]
*Main> [2 # i | i <- [0..1]]
["ab","aa"]
*Main> [3 # i | i <- [0..4]]
["abc","aba","abb","aab","aaa"]
*Main> [4 # i | i <- [0..14]]
["abcd","abca","abcb","abcc","abac","abaa","abab","abbc","abba","abbb","aabc","aaba","aabb","aaab","aaaa"]

(Si el N máximo fuera 25 en lugar de 26, .fromEnumpodría eliminarse, porque B (25) cabe en un bit de 64 bits Int).

Perl 257 + 1 (bandera -p) = 258

Perl 182 + 10 (-pMbignum flags) = 192

($n,$i)=split;@m=[@a=(1)x($n+1)];while($a[2]){push@m,[@a=map{$a[$_]*$_+$a[$_+1]}0..$#a-1]}$_='';$y=1;while($w=pop@m){$c=int($i/($v=$$w[$y]));$c=$y++if($c>=$y);$i-=$c*$v;$_.=chr$c+65}

¡Gracias a dev-nul por guardar muchos bytes! Ahora lo he reescrito en base a lo que aprendí al hacer la versión de CJam.

Calcula la rima en orden alfabético ascendente, 0 indexado.

Dos partes: la Parte 1 es 128 90 bytes y calcula una matriz para la Parte 2. La Parte 2 es 129 92 bytes y hace algunas matemáticas simples para calcular cada letra. Si pudiera deshacerme de la matriz y reemplazarla con dos números simples, ¡podría calcular una sola ruta a través de la matriz para cada número y ahorrar muchos bytes! Al parecer, esa idea no funciona!

Desafortunadamente, no igenera las rimas correctas para valores superiores a 9007199254740992, ¡pero funciona maravillosamente para valores bajos! He agregado la biblioteca Bignum a un costo de 11 bytes. Se ejecuta desde la línea de comandos con perl -pMbignum bell-rhyme.pl. -pMbignum = 10 bytes. También es muy rápido para cualquier valor de entrada.

Oracle SQL 11,2, 412 284 283 bytes

WITH a AS(SELECT CHR(96+LEVEL)d,LEVEL b FROM DUAL CONNECT BY LEVEL<=:i),v(s,c,n)AS(SELECT d,1,1 FROM a WHERE b=1 UNION ALL SELECT s||d,b,LENGTH(REGEXP_REPLACE(s||d,'([a-z])\1+','\1'))FROM v,a WHERE(b<=n OR b=c+1)AND LENGTH(s)<:n)SELECT s FROM v WHERE:n=LENGTH(s)AND:i<=:n ORDER BY 1;

Desafortunadamente, solo tiene una longitud de 8. Cualquier valor mayor da como resultado: ORA-01489: el resultado de la concatenación de cadenas es demasiado largo

Sin golf

WITH a AS(SELECT CHR(96+LEVEL)d,LEVEL b FROM DUAL CONNECT BY LEVEL<=:i),
v(s,c,n) AS
(
  SELECT d,1,1 FROM a WHERE b=1
  UNION ALL
  SELECT s||d,b,LENGTH(REGEXP_REPLACE(s||d,'([a-z])\1+','\1')) 
  FROM v,a 
  WHERE (b<=n OR b=c+1) AND LENGTH(s)<:n
)
SELECT s FROM v WHERE LENGTH(s)=:n AND :i<=:n ORDER BY 1;

La vista a genera: las letras i en la columna a y su valor en b.

La vista recursiva v toma la cadena que se construye como parámetro v, el valor de la última letra usada en c y el valor de la letra más grande usada en n. El parámetro n es igual a la longitud de la cadena sin ninguna letra duplicada, para eso está la expresión regular.

Una letra es válida si su valor es <= el valor de la letra más grande ya utilizada o si es la siguiente letra que se utilizará.

De alguna manera, la consulta necesita la parte LENGTH (s) <: n para ejecutarse, me falta algo en cómo funciona la consulta.

El SELECT principal se encarga de filtrar las entradas no válidas y las cadenas más cortas creadas antes de alcanzar la longitud objetivo.

Versión de 412 bytes

WITH a AS(SELECT * FROM(SELECT d,b,ROW_NUMBER()OVER(PARTITION BY b ORDER BY d)l FROM(SELECT CHR(64+DECODE(MOD(LEVEL,:i),0,:i,MOD(LEVEL,:i)))d,CEIL(LEVEL/:i)b FROM DUAL CONNECT BY LEVEL<=:i*:n))WHERE l<=b),v(s,c,p)AS(SELECT d,1,l FROM a WHERE b=1 UNION ALL SELECT s||d,c+1,l FROM v,a WHERE c+1=b AND(l<=LENGTH(REGEXP_REPLACE(s,'([A-Z])\1+','\1'))OR l=p+1))SELECT s FROM v WHERE LENGTH(s)=:n AND :i<=:n ORDER BY 1;

No intente la consulta de 412 bytes con 26. Pone la base de datos en modo restringido, al menos en mi versión xe que se ejecuta en un contenedor docker en un macbook. Podría probarme los exadata en el trabajo, pero lamentablemente todavía necesito trabajar para vivir.

Mathematica, 136 bytes

(For[j=2^#-1;t=#2,c=1;m=0;x=t;r=If[#>0,++m,c*=m;d=x~Mod~m+1;x=⌊x/m⌋;d]&/@j~IntegerDigits~2;;c<=t,t-=c;--j];FromCharacterCode[r+64])&

Para completar, aquí está mi implementación de referencia de golf. A diferencia de las respuestas existentes, esto no se ejecuta en tiempo polinómico (es exponencial Ncon la base 2), pero cumple con la restricción de tiempo (el peor de los casos aún se ejecutaría en menos de media hora).

La idea es esta:

• Para cada esquema de rima podemos identificar las posiciones donde el carácter máximo hasta ahora aumenta:

  ABCDEFGHDIJDEKBBIJEIKHDFII
  ^^^^^^^^ ^^  ^
  

  Podemos tratar esas marcas como un número binario que facilita la iteración sobre todas esas estructuras. Necesitamos iterar de 2 ^n-1 a 2 ⁿ (o al revés), que es de donde proviene la complejidad exponencial del tiempo.

• Para cada estructura de este tipo, es fácil determinar cuántas cadenas de este tipo hay: solo los espacios entre las marcas se pueden elegir libremente, y el máximo delante del espacio nos dice cuántos caracteres diferentes son válidos en cada posición. Este es un producto simple. Si este número es menor que i, lo restamos i. De lo contrario, hemos encontrado la estructura del esquema de rima solicitado.
• Para enumerar los esquemas en la estructura dada, simplemente representamos i(o lo que queda de ella) como un número de base mixta, donde los pesos de los dígitos están determinados por el número de caracteres permitidos en las posiciones restantes.

Me pregunto si esto permitiría una solución más corta en algunos de los otros idiomas que se enviaron, ya que no requiere ninguna memorización o precomputación.