Sortie de toutes les chaînes

34

Avec un ensemble de lettres, affichez toutes les chaînes constituées de ces lettres. (Ceci est l' étoile Kleene de l'ensemble.) Par exemple, pour {'a','b'}, les chaînes sont:

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

Entrée: une collection non vide de lettres distinctes a..z. Ceux-ci peuvent être des caractères ou des chaînes à caractère unique.

Sortie: Toutes les chaînes de ces lettres, dans n'importe quel ordre, sans répétition. Vous pouvez utiliser des listes de caractères comme des chaînes.

Ceci est une liste infinie, vous pouvez donc la générer par:

  • Courir pour toujours en écrivant de plus en plus de chaînes. Ces chaînes peuvent être écrites dans n’importe quel format, ce qui signifie qu’elles vous permettent de savoir où se termine chaque chaîne, mais elles ne sont pas subdivisées en groupes.
  • Prendre un nombre nen entrée et sortir les premières nchaînes dans n'importe quel format séparé à plat
  • Cédant chaque chaîne à son tour à partir d'un objet générateur
  • Produire un objet infini

Assurez-vous que votre méthode génère finalement chaque chaîne de la sortie, car il est possible de produire une infinité de chaînes à partir de l'ensemble sans jamais accéder à certaines chaînes.

Vous ne pouvez pas le sortir par

  • Produire la nthème donnéen
  • Fournir un oracle d'appartenance qui décide si une chaîne donnée appartient à l'ensemble

Les opérations intégrées sont autorisées, mais je demande aux électeurs d’accorder une attention particulière aux réponses qui implémentent l’opération elles-mêmes par rapport à celles qui reposent principalement sur une commande intégrée.

Afficher l'extrait de code

code-golf string Xnor
la source
@ Cyoce Je ne sais pas ce que vous voulez dire. J'ai précisé que les chaînes doivent être séparées, de sorte que vous pouvez distinguer la chaîne vide de rien.
xnor
Veuillez expliquer pourquoi "produire la Nème chaîne donnée N" n'est pas autorisé.
CalculatriceFeline
4
@CatsAreFluffy C'était un jugement. Je pense que produire la chaîne Nth serait trop facile par rapport aux alternatives et rendrait le défi moins intéressant, notamment parce que certaines langues ont une conversion intégrée à base arbitraire. En outre, je ne pensais pas que cela traduisait l'idée de générer un ensemble infini plutôt que de l'interroger.
xnor
Pouvez-vous expliquer "produire un objet infini"? Cela signifie-t-il que nous pouvons par exemple placer chaque chaîne dans la pile (pour les langages de pile) et la laisser fonctionner "pour toujours", même si aucune sortie ne sera jamais produite car le programme ne se terminera pas?
Luis Mendo
@DonMuesli La sortie sur la pile est-elle une méthode de sortie acceptée pour de tels langages? Et, la pile ne contiendra-t-elle que ces chaînes à un moment donné?
xnor

Réponses:

26

Python 2, 53 56

-3 après avoir réalisé qu'il yield xpeut être utilisé comme expression.

def f(s):yield'';[(yield w+c)for w in f(s)for c in s]
feersum
la source
Un octet plus courte, mais commence à 'aa'plutôt que de '': S=lambda s:(c+w for f in[str,S]for w in f(s)for c in s). Aussi ne fonctionne pas pour l'entrée vide.
Orlp
20

Haskell, 24 octets

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

Produit une liste infinie.

*Main> f "abc"
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa","caa","aba","bba","cba",…
Anders Kaseorg
la source
Dommage (:)<$>s<*>f sdonnerait le mauvais ordre. Il y a f s="":(flip(:)<$>f s<*>s)mais c'est plus long.
xnor
Ouais. J'avais trouvé le 23 octets f s=[]:(f s<**>map(:)s)sauf que ce <**>n'est pas dedans Prelude.
Anders Kaseorg
11

JavaScript (ES6), 61 octets

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

Générateur Python du port de @ feersum. Le letest nécessaire. Économisez 2 octets en utilisant un tableau de compréhension (proposition ES7 échouée, mais fonctionnant dans Firefox 30-57):

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

Version alternative pour 73 octets qui renvoie les premiers néléments fournis par le générateur ci-dessus:

(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)
Neil
la source
JS a des générateurs? : 0000000
Chat le
10

Mathematica, 32 31 octets

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

Modifier:

CatsAreFluffy a gratté un octet.

murphy
la source
8

Perl, 39 37 35 octets

(Décrit d’abord une ancienne version. Le nouveau programme plus court est à la fin)

Comprend +3 pour -alp

Exécuter avec le jeu de caractères sur STDIN, par exemple perl -alp kleene.pl <<< "a b c"

kleene.pl (cette version est 34 + 3 octets):

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

Ajouter +2 pour -F(drop implicite -as'il n'y a pas d'espaces entre les caractères saisis, ou -6 (seulement @a=""avant }) si on met déjà des virgules entre les caractères sur STDIN

Explication:

Les -alpoptions rendent le code efficacement:

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

Comme vous pouvez le constater, <>perl n'est pas seulement utilisé pour readline, mais peut également effectuer un globging de style shell (en fait, dans les perls anciens, il était implémenté en appelant le shell).

Par exemple <{a,b}{1,2}>, s'étendra à"a1","a2","b1","b2"

Donc, si nous avons les éléments, @Fnous avons juste besoin d'ajouter des virgules entre les deux. Le caractère intermédiaire intermédiaire pour l'interpolation est l'espace, qui est stocké dans une variable spéciale $". Donc, mettre $"à ,se transformera "{@F}"en {a,b}si @F=qw(a b)(globs se développent en tant que chaînes)

En fait, j'aurais vraiment aimé faire une boucle avec quelque chose du genre glob"{@F}"x$n++, mais j'ai continué à rencontrer le problème suivant: la première ligne vide n'est pas générée et toutes les solutions de contournement que j'ai trouvées rendaient le code trop long.

Une autre partie essentielle de ce code est donc que si vous utilisez une forboucle to sur un tableau, vous pouvez y insérer des éléments supplémentaires au cours de la boucle et la boucle prendra également en compte ces nouveaux éléments. Donc, si dans la boucle nous sommes par exemple at "ab", nous <{@F}$_>allons développer <{a,b}ab>ce qui devient dans le contexte de liste ("aab", "bab"). Donc, si j'appuie dessus, @ales cordes étendues à gauche deviennent aussi disponibles

Tout ce qu'il me reste à faire, c'est d'amorcer la boucle avec une chaîne vide. Cela se fait en utilisant $#a = 0( ,dans le contexte numérique devient 0) ce qui cause le premier et le seul élément de @adevenir undef qui se comportera comme ""quand je l'utilise

Amélioration

En fait, en effectuant des tests pour cette explication, j'ai trouvé un moyen rapide d'utiliser un glob en pleine croissance qui gère correctement la première entrée vide. Exécuter en tant que perl -ap kleene0.pl <<< "a b"(ajoutez donc 2 octets pour -ap)

kleene0.pl (cette version est 33 + 2 octets):

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

Toutes ces solutions garderont de plus en plus de sorties en mémoire, ce qui entraînera l'échec du programme après un certain temps. Vous pouvez également utiliser des globes perl pour la génération lazy en les utilisant dans un contexte scalaire, mais cela allonge la durée des programmes ....

Ton Hospel
la source
Pouvez-vous s'il vous plaît expliquer ce qui se passe autour de <{@F}$_>:? Merci!
andlrc
6

Pyth, 7

<s^LzQQ

Essayez-le ici

Ceci calcule le produit cartésien de l'entrée avec chaque nombre à partir de 0..n-1, les joint, puis ne conserve que le premier n. Cela expirera en ligne pour les nombres ou les chaînes beaucoup plus gros que 3-4.

Alternativement, pour obtenir une sortie infinie, regardez la réponse de Jakube .

FryAmTheEggman
la source
5

Gelée, 8 à 6 octets

⁷³p$Ȯ¿

Il s'agit d'un lien monadique qui accepte un alphabet et imprime une liste infinie de chaînes. Essayez-le en ligne!

Comment ça marche

⁷³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.

Version alternative, 6 octets (non concurrente)

R’ḃL}ị

Il s'agit d'un lien dyadique qui accepte un alphabet et le nombre souhaité de chaînes en tant qu'arguments gauche et droit, respectivement.

Je considère cette version comme non compétitive, car elle utilise la conversion de base bijective, qui a été mise en œuvre après la mise en sandbox de ce défi. Essayez-le en ligne!

Comment ça marche

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
la source
4

Python 2, 89 84 83 octets

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
la source
Sensationnel. Plus court et sans construit.
Morgan Thrapp
4

CJam, 16 à 10 octets

Merci à jimmy23013 d'avoir économisé 6 octets.

N{eam*_o}h

L'entrée est un argument de ligne de commande par caractère. La sortie est une chaîne sur chaque ligne.

Essayez-le en ligne! (Mais tuez-le immédiatement ...)

Explication

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
la source
3

Pyth, 7 octets

.V0j^zb

Alternative à @fry. Ce programme lit une chaîne et continue à imprimer des chaînes jusqu'à l'infini.

Explication:

.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

Sinon, ce qui suit fonctionnera également. Un peu plus hacky cependant.

u
M^zH7
Jakube
la source
3

Haskell, 33 octets

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

Par exemple, k "xyz"est la liste infinie["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]

Lynn
la source
3

MATL , 10 octets

0cD`G@Z^DT

Essayez-le en ligne! Mais ne le laissez pas fonctionner longtemps, afin d'éviter une charge de calcul importante sur le serveur.

Le programme affiche les chaînes de manière dynamique, chaque chaîne sur une ligne différente.

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
la source
2

Python 3, 95

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

Pourquoi les fonctions itertools doivent-elles avoir des noms aussi longs?

Morgan Thrapp
la source
3
combinations_with_replacementne vaut jamais la peine. Je suis sûr que c'est plus court d'utiliser des boucles. Toujours.
mbomb007
2

Ruby, 65 60 octets

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

De tels noms construits depuis longtemps ...

Poignée de porte
la source
1
Autant que je sache, vous n’avez pas besoin d’espace avant et vous pouvez utiliser p au lieu de.
Fonds de la poursuite de Monica
@QPaysTaxes L'espace ne peut pas être supprimé et fait pappel inspectà ses arguments qui produiraient une sortie comme[] ["a","b"] ["aa", "ab", ...
Doorknob
J'ai mal compris votre réponse. Je pensais qu'il générait un tableau infini et l'imprimait. Cependant, je suis à peu près sûr que sur Array, to_s est associé à inspecter, ainsi les options de vente put et p ont le même résultat. ruby-doc.org/core-2.2.0/Array.html#method-i-to_s WRT l'espace: avez-vous vérifié? Certes, je n'en suis pas certain, mais j'en suis assez sûr.
Le procès de Monica
1

Pyke (commit 31), 10 à 9 octets

=blR.fbtp

Explication:

=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(^)
Bleu
la source
1

Scala, 69

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

Les ruisseaux paresseux sont assez gentils pour ce genre de chose.

Joe K
la source
1

Japt, 50 40 34 28 octets

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

L'entrée est "string", number of items. La sortie est triée par longueur, puis par ordre alphabétique inverse. Testez-le en ligne!

Comment ça marche

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.

Cette version prend un certain temps si vous voulez faire plus de 100 éléments. Si vous voulez une version plus rapide, essayez celle-ci de 32 octets :

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

Cannelle, 6 octets

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

Non en compétition parce que Cinnamon Gum a été fabriqué après ce défi.

Essayez-le en ligne (limite de sortie TIO).

Explication

Le hmet Gomme à la cannelle dans le format et le mode de génération . Le reste de la chaîne se décompresse en [%s]*. Le %sest ensuite remplacé par l'entrée et un générateur est créé, qui génère toutes les chaînes possibles correspondant à l'expression régulière.

un spaghetto
la source
1

05AB1E , 9 octets

g<∞*εÅв¦J

Essayez-le en ligne!

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
la source
0

Python, 55 octets

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

C'est plus long que la solution de 53 octets de feersum , mais cela illustre une méthode différente avec une sortie imprimée. La liste lest mise à jour lorsqu'elle est itérée en ajoutant chaque suffixe d'un caractère de chaque chaîne lue.

C'est également long à utiliser map:

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

La même longueur peut être effectuée dans Python 3, en perdant un caractère print()et en en sauvegardant un en décompressant les entrées.

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

Zsh , 31 octets

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

Essayez-le en ligne!

Imprimez le tableau, puis compressez les arguments avant de procéder à la récurrence. Malgré l'inclusion du nom de la fonction, il s'agit d'un octet plus court que la version itérative:

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