Saída de todas as strings

34

Dado um conjunto de letras, produza todas as strings feitas com essas letras. (Esta é a estrela Kleene do conjunto.) Por exemplo, para {'a','b'}, as strings são:

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

Entrada: uma coleção não vazia de letras distintas a..z. Podem ser caracteres ou cadeias de caracteres únicos.

Saída: todas as strings nessas letras, em qualquer ordem, sem repetições. Você pode usar listas de caracteres como seqüências de caracteres.

Esta é uma lista infinita, para que você possa produzi-la por:

  • Correndo para sempre escrevendo mais e mais strings. Essas cadeias de caracteres podem ser escritas em qualquer formato simples e separado, o que significa que você pode dizer onde cada cadeia termina, mas as cadeias não são subdivididas em grupos.
  • Tomando um número ncomo entrada e emitindo as primeiras nstrings em qualquer formato separado plano
  • Produzindo cada sequência por vez de um objeto gerador
  • Produzindo um objeto infinito

Certifique-se de que seu método acabe produzindo todas as seqüências de caracteres na saída, pois é possível produzir infinitas seqüências de caracteres do conjunto sem nunca chegar a algumas.

Você não pode produzi-lo

  • Produzindo a nth string dadan
  • Fornecer um oráculo de associação que decida se uma determinada sequência pertence ao conjunto

Os internos são permitidos, mas peço aos eleitores que prestem atenção nas respostas que implementam a operação por conta própria das que dependem principalmente de um interno.

Mostrar snippet de código

code-golf string xnor
fonte
@ Cyoce Não sei o que você quer dizer. Esclareci que as seqüências de caracteres devem ser separadas, para que você possa diferenciar a seqüência vazia do nada.
xnor 26/02
Por favor, explique por que "a produção da N-ésima sequência fornecida N" não é permitida.
CalculatorFeline
4
@CatsAreFluffy Foi uma decisão judicial. Acho que produzir a enésima sequência seria muito fácil em comparação com as alternativas e tornaria o desafio menos interessante, especialmente porque alguns idiomas possuem conversão de base arbitrária integrada. Além disso, não achei que capturasse a ideia de gerar um conjunto infinito em vez de consultá-lo.
xnor
Você pode explicar "produzindo um objeto infinito"? Isso significa que podemos, por exemplo, inserir cada string na pilha (para idiomas da pilha) e deixá-la executar "para sempre", mesmo que nenhuma saída seja produzida porque o programa não será concluído?
Luis Mendo
@DonMuesli A saída para a pilha é um método de saída aceito para esses idiomas? E a pilha conterá apenas essas cadeias em algum momento?
Xnor

Respostas:

26

Python 2, 53 56

-3 depois de perceber que isso yield xpode ser usado como uma expressão.

def f(s):yield'';[(yield w+c)for w in f(s)for c in s]
feersum
fonte
Um byte mais curto, mas começa em 'aa'vez de em '': S=lambda s:(c+w for f in[str,S]for w in f(s)for c in s). Também não funciona para a entrada vazia.
orlp 27/02
20

Haskell, 24 bytes

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

Produz uma 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
fonte
Pena (:)<$>s<*>f sque daria a ordem errada. Há, f s="":(flip(:)<$>f s<*>s)mas é mais longo.
xnor 01/03
Sim. Eu tinha encontrado o byte de 23 bytes, f s=[]:(f s<**>map(:)s)exceto que <**>não está Prelude.
Anders Kaseorg 01/01
11

JavaScript (ES6), 61 bytes

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

Porto do gerador Python do @ feersum. O leté necessário. Salve 2 bytes usando uma compreensão de matriz (falha na proposta do ES7, mas funciona no Firefox 30-57):

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

Versão alternativa para 73 bytes que retorna os primeiros nelementos gerados pelo gerador acima:

(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)
Neil
fonte
JS tem geradores? : 0000000
cat
10

Mathematica, 32 31 Bytes

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

Editar:

CatsAreFluffy raspou um byte.

Murphy
fonte
8

Perl, 39 37 35 bytes

(Primeiro descreve uma versão mais antiga. O novo programa mais curto está no final)

Inclui +3 para -alp

Execute com o conjunto de caracteres em STDIN, por exemplo perl -alp kleene.pl <<< "a b c"

kleene.pl (esta versão é 34 + 3 bytes):

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

Adicione +2 para -F(solte implícito -ase não houver espaços entre os caracteres de entrada ou -6 (somente @a=""antes })) se já colocarmos vírgulas entre os caracteres em STDIN

Explicação:

As -alpopções tornam o código eficaz:

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

Como você pode ver <>, o perl não é usado apenas para o readline, mas também pode fazer globbing no estilo do shell (de fato, nos perls antigos, foi implementado chamando o shell).

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

Portanto, se tivermos os elementos @F, basta adicionar vírgulas entre elas. O caractere padrão entre interpolações é o espaço, que é armazenado na variável especial $". Assim a definição $"de ,girará "{@F}"em {a,b}se @F=qw(a b)(globs expandir como cordas)

Na verdade, eu realmente gostaria de fazer algo assim glob"{@F}"x$n++, mas continuei com o problema de que a primeira linha vazia não é gerada e todas as soluções alternativas que encontrei tornaram o código muito longo.

Portanto, outra parte essencial desse código é que, se você usar um forloop em um array, poderá inserir elementos extras durante o loop e o loop também capturará esses novos elementos. Portanto, se no loop estamos, por exemplo, no elemento "ab", ele <{@F}$_>será expandido para o <{a,b}ab>qual o contexto da lista se tornará ("aab", "bab"). Então, se eu pressionar isso @a, as cordas estendidas uma para a esquerda também ficarão disponíveis

Tudo o que ainda preciso fazer é preparar o loop com uma string vazia. Isso é feito usando $#a = 0( ,no contexto numérico torna-se 0) o que faz com que o primeiro e único elemento @ase torne indefinido, que se comportará como ""quando eu o usar

Melhoria

De fato, fazendo testes para essa explicação, encontrei uma maneira curta de usar uma glob crescente que lida adequadamente com a primeira entrada vazia. Executar como perl -ap kleene0.pl <<< "a b"(adicione 2 bytes para -ap)

kleene0.pl (esta versão tem 33 + 2 bytes):

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

Todas essas soluções manterão cada vez mais a saída na memória e isso fará com que o programa falhe após algum tempo. Você também pode usar globs perl para geração lenta usando-os no contexto escalar, mas isso torna os programas mais longos ....

Ton Hospel
fonte
Você pode explicar o que está acontecendo <{@F}$_>:? Obrigado!
28716 Andlrc
6

Pitão, 7

<s^LzQQ

Experimente aqui

Isso calcula o produto cartesiano da entrada com cada número de 0..n-1, junta-se a eles e depois mantém apenas o primeiro n. Isso excederá o tempo limite on-line para números ou seqüências de caracteres muito maiores que 3-4.

Como alternativa, para obter uma saída infinita, observe a resposta de Jakube .

FryAmTheEggman
fonte
5

Geléia, 8 6 bytes

⁷³p$Ȯ¿

Este é um link monádico que aceita um alfabeto e imprime uma lista infinita de strings. Experimente online!

Como 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.

Versão alternativa, 6 bytes (não concorrente)

R’ḃL}ị

Esse é um link diádico que aceita um alfabeto e o número desejado de strings como argumentos esquerdo e direito, respectivamente.

Considero esta versão não concorrente, pois usa a conversão de base bijetiva, que foi implementada após o desafio ter sido sandboxed. Experimente online!

Como 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
fonte
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
fonte
Uau. Mais curto e sem builtins.
23816 Morgan Thrapp
4

CJam, 16 10 bytes

Obrigado a jimmy23013 por salvar 6 bytes.

N{eam*_o}h

Entrada é um argumento da linha de comandos por caractere. Saída é uma string em cada linha.

Experimente online! (Mas mate-o imediatamente ...)

Explicação

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
fonte
3

Pitão, 7 bytes

.V0j^zb

Alternativa ao @fry. Este programa lê uma string e continua imprimindo strings até o infinito.

Explicação:

.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, o seguinte também funcionará. Um pouco mais hacky embora.

u
M^zH7
Jakube
fonte
3

Haskell, 33 bytes

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

Por exemplo, k "xyz"é a lista infinita["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]

Lynn
fonte
3

MATL , 10 bytes

0cD`G@Z^DT

Experimente online! Mas não deixe por muito tempo, para evitar grande carga computacional no servidor.

O programa exibe as seqüências dinamicamente, cada sequência em uma linha 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
fonte
2

Python 3, 95

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

Por que as funções do itertools devem ter nomes tão longos?

Morgan Thrapp
fonte
3
combinations_with_replacementnunca vale a pena. Tenho certeza de que é mais curto usar loops. Sempre.
mbomb007
2

Ruby, 65 60 bytes

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

Nomes tão compridos ...

Maçaneta da porta
fonte
1
AFAIK Você não precisa do espaço antes do & e pode usar p em vez de colocar.
Fund Monica's Lawsuit
@QPaysTaxes O espaço não pode ser descartado e pchama inspectseus argumentos que produziriam saída como[] ["a","b"] ["aa", "ab", ...
Doorknob
Eu não entendi sua resposta. Eu pensei que estava gerando uma matriz infinita e imprimindo-a. No entanto, tenho certeza de que, em Array, to_s é alias para inspecionar, portanto, put e p têm a mesma saída. ruby-doc.org/core-2.2.0/Array.html#method-i-to_s WRT o espaço: Você verificou? É certo que não tenho certeza, mas tenho certeza disso.
Fund Monica's Lawsuit
1

Pyke (confirmação 31), 10 9 bytes

=blR.fbtp

Explicação:

=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
fonte
1

Scala, 69

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

Fluxos preguiçosos são muito bons para esse tipo de coisa.

Joe K
fonte
1

Japt, 50 40 34 28 bytes

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

Entrada é "string", number of items. A saída é classificada por comprimento e, em seguida, inverta a ordem do alfabeto. Teste online!

Como 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 versão demora um pouco se você quiser fazer mais de 100 itens. Se você deseja uma versão mais rápida, tente esta de 32 bytes :

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

Goma de canela, 6 bytes

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

Não concorrente porque o chiclete de canela foi produzido após esse desafio.

Experimente online (o TIO limita a saída).

Explicação

A hcoloca canela Gum em formato eo modo de gerar . O restante da string é descompactado para [%s]*. O %sé então substituído pela entrada e um gerador é criado que gera todas as seqüências possíveis correspondentes ao regex.

um spaghetto
fonte
1

05AB1E , 9 bytes

g<∞*εÅв¦J

Experimente online!

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
Grimmy
fonte
0

Python, 55 bytes

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

Isso é mais longo que a solução de 53 bytes do feersum , mas ilustra um método diferente com a saída impressa. A lista lé atualizada enquanto é iterada, acrescentando cada sufixo de um caractere de cada sequência que é lida.

É igualmente longo para usar map:

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

O mesmo comprimento pode ser feito no Python 3, perdendo um caractere print()e salvando-o ao descompactar a entrada.

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

Zsh , 31 bytes

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

Experimente online!

Imprima a matriz e feche os argumentos antes de repetir. Apesar de incluir o nome da função, este é um byte menor que a versão iterativa:

for ((;;))<<<${(F)a}&&a=($^a$^@)
GammaFunction
fonte