Salida de todas las cadenas

34

Dado un conjunto de letras, genera todas las cadenas hechas de esas letras. (Esta es la estrella de Kleene del conjunto). Por ejemplo, para {'a','b'}, las cadenas son:

'', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', 'aab', ...

Entrada: una colección no vacía de letras distintas a..z. Estos pueden ser caracteres o cadenas de un solo carácter.

Salida: todas las cadenas en esas letras, en cualquier orden, sin repeticiones. Puede usar listas de caracteres como cadenas.

Esta es una lista infinita, por lo que puede generarla de la siguiente manera:

  • Corriendo para siempre escribiendo más y más cadenas. Estas cadenas se pueden escribir en cualquier formato separado, lo que significa que puede saber dónde termina cada cadena, pero las cadenas no se subdividen en grupos.
  • Tomar un número ncomo entrada y salida de las primeras ncadenas en cualquier formato plano separado
  • Ceder cada cuerda a su vez de un objeto generador
  • Produciendo un objeto infinito

Asegúrese de que su método finalmente produzca todas las cadenas en la salida, ya que es posible producir infinitas cadenas del conjunto sin llegar a algunas cadenas.

Es posible que no la salida por

  • Produciendo la ncadena th dadan
  • Proporcionar un oráculo de membresía que decida si una cadena dada pertenece al conjunto

Los elementos integrados están permitidos, pero les pido a los votantes que presten atención a las respuestas que implementan la operación por sí mismas en lugar de las que dependen principalmente de un elemento integrado.

Mostrar fragmento de código

code-golf string xnor
fuente
@Cyoce No estoy seguro de lo que quieres decir. Aclaré que las cadenas deben estar separadas, para que pueda distinguir la cadena vacía de la nada.
xnor
Explique por qué no está permitido "producir la enésima cadena dada N".
CalculatorFeline
44
@CatsAreFluffy Fue una decisión judicial. Creo que producir la enésima cadena sería demasiado fácil en comparación con las alternativas y haría que el desafío fuera menos interesante, especialmente porque algunos idiomas tienen una conversión de base arbitraria incorporada. Además, no pensé que capturara la idea de generar un conjunto infinito en lugar de consultarlo.
xnor
¿Puedes explicar "producir un objeto infinito"? ¿Eso significa que, por ejemplo, podemos insertar cada cadena en la pila (para los idiomas de la pila) y dejar que se ejecute "para siempre", incluso si no se producirá ningún resultado porque el programa no terminará?
Luis Mendo
@DonMuesli ¿La salida a la pila es un método de salida aceptado para dichos idiomas? ¿Y la pila contendrá solo estas cadenas en algún momento?
xnor

Respuestas:

26

Pitón 2, 53 56

-3 después de darse cuenta de que yield xse puede usar como una expresión.

def f(s):yield'';[(yield w+c)for w in f(s)for c in s]
Feersum
fuente
Un byte más corto, pero se inicia en 'aa'vez de en '': S=lambda s:(c+w for f in[str,S]for w in f(s)for c in s). Tampoco funciona para la entrada vacía.
orlp
20

Haskell, 24 bytes

f s=[]:[b:a|a<-f s,b<-s]

Produce una lista infinita.

*Main> f "abc"
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa","caa","aba","bba","cba",…
Anders Kaseorg
fuente
Lástima (:)<$>s<*>f sque daría el orden equivocado. Hay f s="":(flip(:)<$>f s<*>s)pero es más largo.
xnor
Sí. Encontré el byte de 23, f s=[]:(f s<**>map(:)s)excepto que <**>no está en Prelude.
Anders Kaseorg
11

JavaScript (ES6), 61 bytes

function*g(s){yield'';for(let r of g(s))for(c of s)yield c+r}

Puerto del generador Python de @feersum. El letes necesario. Ahorre 2 bytes utilizando una comprensión de matriz (propuesta ES7 fallida, pero funciona en Firefox 30-57):

function*g(s){yield'';[for(r of g(s))for(c of s)yield c+r]}

Versión alternativa para 73 bytes que devuelve los primeros nelementos producidos por el generador anterior:

(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)
Neil
fuente
JS tiene generadores? : 0000000
gato
10

Mathematica, 32 31 Bytes

Do[Echo/@#~Tuples~n,{n,0,∞}]&

Editar:

CatsAreFluffy raspó un byte.

murphy
fuente
8

Perl, 39 37 35 bytes

(Primero describe una versión anterior. El nuevo programa más corto está al final)

Incluye +3 para -alp

Ejecutar con el conjunto de caracteres en STDIN, p. Ej. perl -alp kleene.pl <<< "a b c"

kleene.pl (esta versión tiene 34 + 3 bytes):

$#a=$"=","}for(@a){push@a,<{@F}$_>

Agregue +2 para -F(descarte implícito -asi no hay espacios entre los caracteres de entrada, o -6 (solo @a=""antes} ) si ya ponemos comas entre los caracteres en STDIN

Explicación:

Las -alpopciones hacen que el código sea efectivo:

BEGIN { $/ = "\n"; $\ = "\n"; }
LINE: while (defined($_ = <ARGV>)) {
    chomp $_;
    our @F = split(' ', $_, 0);
    $#a = $" = ',';
}
foreach $_ (@a) {
    use File::Glob ();
    push @a, glob('{' . join($", @F) . '}' . $_);
}

Como puede ver <>en perl, no solo se usa para readline, sino que también puede hacer globbing de estilo shell (de hecho, en perls antiguos se implementó llamando al shell).

Por ejemplo <{a,b}{1,2}>se expandirá a"a1","a2","b1","b2"

Entonces, si tenemos los elementos @F, solo necesitamos agregar comas en el medio. El carácter intermedio predeterminado para la interpolación es el espacio, que se almacena en una variable especial $". Por lo tanto, establecer $"a ,se convertirá "{@F}"en {a,b}if @F=qw(a b)(los globos se expanden como cadenas)

De hecho, me hubiera gustado buclear con algo como glob"{@F}"x$n++ , pero seguí encontrándome con el problema de que la primera línea vacía no se genera y todas las soluciones que encontré hicieron que el código fuera demasiado largo.

Entonces, otra parte esencial de este código es que si usa un forbucle para pasar sobre una matriz, puede empujar elementos adicionales durante el ciclo y el ciclo también recogerá estos elementos nuevos. Entonces, si en el ciclo estamos, por ejemplo, en el elemento "ab", <{@F}$_>se expandirá a lo <{a,b}ab>que se convierte en el contexto de la lista ("aab", "bab"). Entonces, si presiono esto @a, las cuerdas extendidas una a la izquierda también estarán disponibles

Todo lo que necesito hacer es preparar el bucle con una cadena vacía. Eso se hace usando $#a = 0( ,en contexto numérico se convierte 0) lo que hace que el primer y único elemento de se @aconvierta en undef, que se comportará como ""cuando lo uso

Mejora

De hecho, al hacer pruebas para esta explicación, encontré una forma corta de usar un globo creciente que maneja adecuadamente la primera entrada vacía. Ejecutar como perl -ap kleene0.pl <<< "a b"(así que agregue 2 bytes para -ap)

kleene0.pl (esta versión tiene 33 + 2 bytes):

$"=",";print<$z,>;$z.="{@F}";redo

Todas estas soluciones mantendrán más y más de la salida en la memoria y eso hará que el programa falle después de un tiempo. También puede usar perl globs para la generación perezosa al usarlos en contexto escalar, pero eso hace que los programas sean más largos ...

Ton Hospel
fuente
¿Puedes explicar qué está pasando <{@F}$_>? ¡Gracias!
andlrc
6

Pyth, 7

<s^LzQQ

Pruébalo aquí

Esto calcula el producto cartesiano de la entrada con cada número de 0..n-1, los une y luego solo conserva el primero n. Esto agota el tiempo de espera en línea para números o cadenas que son mucho más grandes que 3-4.

Alternativamente, para obtener una salida infinita, mira la respuesta de Jakube .

FryAmTheEggman
fuente
5

Jalea, 8 6 bytes

⁷³p$Ȯ¿

Este es un enlace monádico que acepta un alfabeto e imprime una lista infinita de cadenas. Pruébalo en línea!

Cómo funciona

⁷³p$Ȯ¿    Monadic link. Argument: A (alphabet)

⁷         Set the return value to '\n'.
     ¿    While loop.
            Condition:
    Ȯ         Print the current return value and return it (always truthy).
            Body:
   $          Combine the two links to the left into a single, monadic link.
 ³              Yield A.
  p             Perform the Cartesian product of A and the current return value,
                updating the return value in the process.

Versión alternativa, 6 bytes (no competitiva)

R’ḃL}ị

Este es un enlace diádico que acepta un alfabeto y el número deseado de cadenas como argumentos izquierdo y derecho, respectivamente.

Considero que esta versión no es competitiva, ya que utiliza la conversión de base biyectiva, que se ha implementado después de que este desafío se haya aislado. Pruébalo en línea!

Cómo funciona

R’ḃL}ị    Dyadic link. Arguments: n (integer), A (alphabet)

R         Range; yield [1, ..., n].
 ’        Decrement; yield [0, ..., n-1].
   L}     Yield l, the length of A.
  ḃ       Convert every i in [0, ..., n-1] to bijective base l.
     ị    For each array of digits, retrieve the corresponding characters of A.
Dennis
fuente
4

Python 2, 89 84 83 bytes

x,n=input()
l=len(x)
for i in range(n):
 s=''
 while i:i-=1;s+=x[i%l];i/=l
 print s
Dennis
fuente
Guau. Más corto y sin builtins.
Morgan Thrapp
4

CJam, 16 10 bytes

Gracias a jimmy23013 por guardar 6 bytes.

N{eam*_o}h

La entrada es un argumento de línea de comando por carácter. La salida es una cadena en cada línea.

Pruébalo en línea! (Pero mátalo inmediatamente ...)

Explicación

N      e# Push [\n]. At each step this array will contain all strings of length N,
       e# each followed by a linefeed.
{      e# Infinite loop...
  ea   e#   Read command-line arguments.
  m*   e#   Cartesian product: pairs each letter with each string in the list.
  _o   e#   Output all the strings of the current length.
}h
Martin Ender
fuente
3

Pyth, 7 bytes

.V0j^zb

Alternativa a @fry. Este programa lee una cadena y sigue imprimiendo cadenas hasta el infinito.

Explicación:

.V0      for b in (0 to infinity):
    ^zb     compute all strings of length b consisting of the input alphabet
   j        print each one on a separate line

Alternativamente, lo siguiente también funcionará. Aunque un poco más hacky.

u
M^zH7
Jakube
fuente
3

Haskell, 33 bytes

k u=do s<-[0..];mapM(\_->u)[1..s]

Por ejemplo, k "xyz"es la lista infinita["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]

Lynn
fuente
3

MATL , 10 bytes

0cD`G@Z^DT

Pruébalo en línea! Pero no lo deje funcionando por mucho tiempo, para evitar una gran carga computacional en el servidor.

El programa muestra las cadenas dinámicamente, cada cadena en una línea diferente.

0cD             % force display of a newline to represent the empty string
   `      T     % infinite do-while loop
    G           % push input, or nothing if no input has been taken yet
     @          % push iteration. Gives 1, 2,... in each iteration
      Z^        % Cartesian power. In the first iteration takes input implicitly 
       D        % display
Luis Mendo
fuente
2

Pitón 3, 95

from itertools import*
def f(x,l=0):
 while 1:print(*combinations_with_replacement(x*l,l));l+=1

¿Por qué las funciones de itertools tienen nombres tan largos?

Morgan Thrapp
fuente
3
combinations_with_replacementnunca vale la pena Estoy bastante seguro de que es más corto usar bucles. Siempre.
mbomb007
2

Ruby, 65 60 bytes

->a{n=-1;loop{puts a.repeated_permutation(n+=1).map &:join}}

Dichos nombres tan largos ...

Pomo de la puerta
fuente
1
AFAIK No necesitas el espacio antes y puedes usar p en lugar de put.
Financia la demanda de Mónica el
@QPaysTaxes El espacio no puede descartarse, y precurre inspecta sus argumentos que producirían resultados como[] ["a","b"] ["aa", "ab", ...
Doorknob
No entendí tu respuesta. Pensé que estaba generando una matriz infinita e imprimiéndola. Sin embargo, estoy bastante seguro de que en Array, to_s tiene un alias para inspeccionar, por lo que put y p tienen la misma salida. ruby-doc.org/core-2.2.0/Array.html#method-i-to_s WRT el espacio: ¿Ha verificado? Es cierto que no estoy seguro, pero estoy bastante seguro de ello.
Financia la demanda de Mónica el
1

Pyke (commit 31), 10 9 bytes

=blR.fbtp

Explicación:

=b         -    set characters for base conversion to eval_or_not(input())
  l        -   len(^)
   R      -  [^, eval_or_not(input()]
    .f    - first_n(^)
      b   -    conv_base(^)
       t  -   ^[-1]
        p -  print(^)
Azul
fuente
1

Scala, 69

def f[A](s:Set[A]):Stream[List[A]]=Nil#::f(s).flatMap(x=>s.map(_::x))

Las secuencias diferidas son bastante agradables para este tipo de cosas.

Joe K
fuente
1

Japt, 50 40 34 28 bytes

V²o ®s1+Ul)£UgXnH)¯X¦0}Ãâ ¯V

Entrada es "string", number of items. La salida se ordena por longitud, luego en orden inverso del alfabeto. ¡Pruébelo en línea!

Cómo funciona

V²  o ®   s1+Ul)£  UgXnH)¯  X¦ 0}Ã â ¯  V
Vp2 o mZ{Zs1+Ul)mX{UgXnH)s0,X!=0}} â s0,V

Vp2 o      // Create the range [0..V²).
mZ{     }  // Map each item Z in this range to:
Zs1+Ul)    //  Take the base-(1+U.length) representation of Z.
mX{     }  //  Map each char X in this to:
XnH        //   Parse X as a base-32 number.
Ug   )     //   Take the char at index -^ in U.
s0,X!=0    //   If X is 0, slice it to an empty string.
â          // Uniquify the result.
s0,V       // Slice to the first V items.

Esta versión lleva un tiempo si desea hacer más de 100 elementos. Si quieres una versión más rápida, prueba esta de 32 bytes :

V*2 o ms1+Ul)f@!Xf'0î£UgXnH}ïV
ETHproducciones
fuente
1

Chicle de canela, 6 bytes

0000000: 6801 301c e74b                           h.0..K

No compite porque Cinnamon Gum se hizo después de este desafío.

Pruébelo en línea (TIO limita la salida).

Explicación

El hpone Cinnamon Gum en formato y modo de generación . El resto de la cadena se descomprime a [%s]*. La %scontinuación, se sustituye con la entrada, y un generador se crea que las salidas de todas las cadenas posibles que concuerden con la expresión regular.

un espagueti
fuente
1

05AB1E , 9 bytes

g<∞*εÅв¦J

Pruébalo en línea!

g             # length of the input
 <            # - 1
  ∞           # infinite list [1, 2, 3, …]
   *          # multiply each by the length-1
    ε         # for each:
     Åв       #  custom base conversion, using the input as the list of digits
       ¦      #  chop off the first digit
        J     #  join the rest to a string
Mugriento
fuente
0

Python, 55 bytes

s=input();l=['']
for x in l:print x;l+=[x+c for c in s]

Esto es más largo que la solución de 53 bytes de feersum , pero ilustra un método diferente con salida impresa. La listal se actualiza mientras se repite, agregando cada sufijo de un carácter de cada cadena que se lee.

Es igualmente largo de usar map:

s=input();l=['']
for x in l:print x;l+=map(x.__add__,s)

Se puede hacer la misma longitud en Python 3, perdiendo un carácter print()y guardando uno al desempaquetar la entrada.

s,*l=input(),''
for x in l:print(x);l+=[x+c for c in s]
xnor
fuente
0

Zsh , 31 bytes

f(){<<<${(F)a};a=($^a$^@);f $@}

Pruébalo en línea!

Imprima la matriz, luego comprima los argumentos antes de recurrir. A pesar de incluir el nombre de la función, este es un byte más corto que la versión iterativa:

for ((;;))<<<${(F)a}&&a=($^a$^@)
Función Gamma
fuente