Biorąc pod uwagę zestaw liter, wypisz wszystkie ciągi znaków z tych liter. (To jest gwiazda Kleene zestawu.) Na przykład {'a','b'}ciągi:

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

Dane wejściowe: niepusty zbiór wyraźnych liter a..z. Mogą to być znaki lub ciągi jednoznakowe.

Wyjście: wszystkie ciągi w tych literach, w dowolnej kolejności, bez powtórzeń. Możesz używać list znaków jako ciągów znaków.

To jest nieskończona lista, więc możesz wygenerować ją przez:

• Ciągłe pisanie coraz większej liczby łańcuchów. Ciągi te można zapisać w dowolnym formacie z separacją płaską, co oznacza, że ​​można powiedzieć, gdzie kończy się każdy ciąg, ale ciągi te nie są podzielone na grupy.
• Biorąc liczbę njako dane wejściowe i wyprowadzając pierwsze nciągi znaków w dowolnym formacie z płaską separacją
• Uzyskanie każdego łańcucha z kolei z obiektu generatora
• Produkcja nieskończonego obiektu

Upewnij się, że twoja metoda w końcu generuje każdy ciąg na wyjściu, ponieważ możliwe jest wygenerowanie nieskończenie wielu ciągów ze zbioru, nigdy nie przechodząc do niektórych ciągów.

Nie możesz tego wygenerować

• Wytworzenie npodanego ciągu thn
• Dostarczenie wyroczni członkowskiej, która decyduje, czy dany ciąg należy do zestawu

Wbudowane są dozwolone, ale proszę wyborców o zwrócenie uwagi na odpowiedzi, które same wykonują operację, zamiast tych, które w większości opierają się na wbudowanym.

var QUESTION_ID=74273,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/74273/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Python 2, 53 56

-3 po uświadomieniu sobie, że yield xmożna go użyć jako wyrażenia.

def f(s):yield'';[(yield w+c)for w in f(s)for c in s]

Haskell, 24 bajty

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

Tworzy nieskończoną listę.

*Main> f "abc"
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa","caa","aba","bba","cba",…

JavaScript (ES6), 61 bajtów

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

Port generatora Python @ feersum. Jest letto konieczne. Zaoszczędź 2 bajty, używając rozumienia tablicowego (nieudana propozycja ES7, ale działa w przeglądarce Firefox 30-57):

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

Alternatywna wersja dla 73 bajtów, która zwraca pierwsze nelementy wygenerowane przez powyższy generator:

(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)

Mathematica, 32 31 bajtów

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

Edytować:

CatsAreFluffy zeskrobał jeden bajt.

Perl, 39 37 35 bajtów

(Najpierw opisuje starszą wersję. Nowy krótszy program jest na końcu)

Obejmuje +3 za -alp

Uruchom z zestawem znaków na STDIN, np perl -alp kleene.pl <<< "a b c"

kleene.pl (ta wersja ma 34 + 3 bajty):

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

Dodaj +2 dla -F(niejawnie upuść, -ajeśli nie ma spacji między znakami wejściowymi lub -6 (tylko @a=""wcześniej }), jeśli już wstawiamy przecinki między znakami na STDIN

Wyjaśnienie:

Te -alpopcje skutecznie wprowadzać kod:

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

Jak widać <>w perlu, jest on używany nie tylko do readline, ale może także wykonywać operacje globowania w stylu powłoki (w rzeczywistości w starożytnych perlach było to realizowane przez wywołanie powłoki).

Na przykład <{a,b}{1,2}>rozwinie się do"a1","a2","b1","b2"

Więc jeśli mamy elementy @F, wystarczy dodać przecinki między nimi. Domyślnym znakiem między interpolacją jest spacja, która jest przechowywana w specjalnej zmiennej $". Więc ustawienie $"na ,zmieni się "{@F}"w {a,b}if @F=qw(a b)(globusy rozwijają się jako łańcuchy)

W rzeczywistości chciałbym zapętlić się z czymś takim glob"{@F}"x$n++, ale ciągle napotykałem problem, że pierwsza pusta linia nie jest generowana, a wszystkie znalezione obejścia spowodowały, że kod był zbyt długi.

Kolejną istotną częścią tego kodu jest to, że jeśli użyjesz forpętli nad tablicą, możesz wcisnąć na nią dodatkowe elementy podczas pętli, a pętla również odbierze te nowe elementy. Jeśli więc w pętli znajdujemy się np. W elemencie "ab", <{@F}$_>rozwiniemy się do <{a,b}ab>kontekstu listy ("aab", "bab"). Więc jeśli je @apopchnę, struny rozszerzone po lewej stronie staną się dostępne

Muszę tylko zalać pętlę pustym łańcuchem. Odbywa się to za pomocą $#a = 0( ,w kontekście numerycznym staje się 0), co powoduje, że pierwszy i jedyny element @astaje się undef, który zachowuje się tak, jak ""go używam

Poprawa

W rzeczywistości, wykonując testy dla tego wyjaśnienia, znalazłem krótki sposób na użycie rosnącego globu, który poprawnie obsługuje pierwszy pusty wpis. Uruchom jako perl -ap kleene0.pl <<< "a b"(więc dodaj 2 bajty dla -ap)

kleene0.pl (ta wersja to 33 + 2 bajty):

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

Wszystkie te rozwiązania będą utrzymywały coraz więcej danych wyjściowych w pamięci, co po pewnym czasie spowoduje awarię programu. Możesz także używać globów Perla do leniwego generowania, używając ich w kontekście skalarnym, ale to wydłuża programy ...

Pyth, 7

<s^LzQQ

Wypróbuj tutaj

To oblicza iloczyn kartezjański danych wejściowych z każdą liczbą od 0..n-1, łączy je, a następnie zachowuje tylko pierwszą n. Spowoduje to przekroczenie limitu czasu online dla liczb lub ciągów, które są znacznie większe niż 3-4.

Alternatywnie, aby uzyskać nieskończoną moc wyjściową, spójrz na odpowiedź Jakube .

Galaretka, 8 6 bajtów

⁷³p$Ȯ¿

Jest to monadyczny link, który akceptuje alfabet i drukuje nieskończoną listę ciągów. Wypróbuj online!

Jak to działa

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

Wersja alternatywna, 6 bajtów (niekonkurująca)

R’ḃL}ị

To diademiczne łącze akceptuje alfabet i pożądaną liczbę ciągów znaków odpowiednio jako lewy i prawy argument.

Uważam tę wersję za niekonkurencyjną, ponieważ wykorzystuje ona dwukierunkową konwersję bazy, która została zaimplementowana po piaskownicy tego wyzwania. Wypróbuj online!

Jak to działa

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.

Python 2, 89 84 83 bajtów

x,n=input()
l=len(x)
for i in range(n):
 s=''
 while i:i-=1;s+=x[i%l];i/=l
 print s

CJam, 16 lat 10 bajtów

Dzięki jimmy23013 za oszczędność 6 bajtów.

N{eam*_o}h

Dane wejściowe to jeden argument wiersza polecenia na znak. Dane wyjściowe to jeden ciąg w każdej linii.

Wypróbuj online!(Ale zabij to natychmiast ...)

Wyjaśnienie

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

Pyth, 7 bajtów

.V0j^zb

Alternatywa dla @ fry. Ten program odczytuje ciąg znaków i drukuje ciągi aż do nieskończoności.

Wyjaśnienie:

.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

Alternatywnie będą również działać następujące. Trochę bardziej zuchwały.

u
M^zH7

Haskell, 33 bajty

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

Przykładem k "xyz"jest lista nieskończona["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]

MATL , 10 bajtów

0cD`G@Z^DT

Wypróbuj online!Ale nie pozostawiaj go długo uruchomionego, aby uniknąć dużego obciążenia obliczeniowego na serwerze.

Program wyświetla ciągi dynamicznie, każdy ciąg w innej linii.

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

Python 3, 95

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

Dlaczego funkcje itertools muszą mieć tak długie nazwy.

Rubinowy, 65 60 bajtów

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

Takie długie wbudowane nazwy ...

Pyke (zatwierdzenie 31), 10 9 bajtów

=blR.fbtp

Wyjaśnienie:

=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(^)

Scala, 69

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

Leniwe strumienie są całkiem miłe dla tego rodzaju rzeczy.

Japt, 50 40 34 28 bajtów

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

Dane wejściowe to "string", number of items. Dane wyjściowe są sortowane według długości, a następnie w odwrotnej kolejności alfabetycznej. Przetestuj online!

Jak to działa

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.

Ta wersja zajmuje trochę czasu, jeśli chcesz zrobić więcej niż 100 pozycji. Jeśli chcesz szybszej wersji, wypróbuj tę 32-bajtową wersję :

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

Guma cynamonowa, 6 bajtów

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

Nie konkuruje, ponieważ guma cynamonowa powstała po tym wyzwaniu.

Wypróbuj online (TIO ogranicza moc wyjściową).

Wyjaśnienie

hStawia Cinnamon Gum w formacie i tryb generowania . Reszta ciągu dekompresuje się do [%s]*. Następnie %sjest zamieniany na wejście i tworzony jest generator, który wypisuje wszystkie możliwe ciągi pasujące do wyrażenia regularnego.

05AB1E , 9 bajtów

g<∞*εÅв¦J

Wypróbuj 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

Python, 55 bajtów

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

Jest to dłuższe niż 53-bajtowe rozwiązanie Feersum , ale ilustruje inną metodę z wydrukami . Listal jest aktualizowana podczas iteracji, dodając każdy jednoznakowy przyrostek każdego czytanego ciągu.

Równie długi jest czas użycia map:

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

Tę samą długość można wykonać w Pythonie 3, tracąc znak print()i zapisując go przez rozpakowanie danych wejściowych.

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

Zsh , 31 bajtów

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

Wypróbuj online!

Wydrukuj tablicę, a następnie spakuj argumenty przed rekurencją. Pomimo podania nazwy funkcji jest to o jeden bajt krótszy niż wersja iteracyjna:

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