Keluarkan semua string

34

Diberikan seperangkat surat, output semua string yang terbuat dari surat-surat itu. (Ini adalah bintang Kleene dari set.) Misalnya, untuk {'a','b'}, string adalah:

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

Input: Kumpulan huruf berbeda yang tidak kosong a..z. Ini mungkin karakter atau string karakter tunggal.

Output: Semua string dalam surat-surat itu, dalam urutan apa pun, tanpa pengulangan. Anda dapat menggunakan daftar karakter sebagai string.

Ini adalah daftar tanpa batas, sehingga Anda dapat menampilkannya dengan:

  • Berlari selamanya menulis lebih banyak dan lebih banyak string. String ini dapat ditulis dalam format terpisah apa pun, yang berarti bahwa Anda dapat mengetahui di mana setiap string berakhir, tetapi string tidak dibagi lagi menjadi grup.
  • Mengambil nomor nsebagai input dan menghasilkan nstring pertama dalam format apa pun yang terpisah datar
  • Menghasilkan setiap string pada gilirannya dari objek generator
  • Memproduksi objek tanpa batas

Pastikan bahwa metode Anda pada akhirnya menghasilkan setiap string dalam output, karena dimungkinkan untuk menghasilkan banyak string dari set sementara tidak pernah sampai ke beberapa string.

Anda tidak dapat menampilkannya dengan

  • Memproduksi nstring th diberikann
  • Memberikan oracle keanggotaan yang memutuskan apakah string yang diberikan milik set

Built-in diperbolehkan, tetapi saya meminta pemilih untuk memperhatikan jawaban yang mengimplementasikan operasi itu sendiri atas yang sebagian besar bergantung pada built-in.

Tampilkan cuplikan kode

code-golf string Tidak
sumber
@Cyoce Tidak yakin apa yang Anda maksud. Saya mengklarifikasi bahwa string harus dipisahkan, sehingga Anda dapat membedakan string kosong dari nol.
xnor
Tolong jelaskan mengapa "menghasilkan string ke-N yang diberikan N" tidak diizinkan.
CalculatorFeline
4
@CatsAreFluffy Itu adalah panggilan penilaian. Saya pikir memproduksi string ke-N akan terlalu mudah dibandingkan dengan alternatifnya dan membuat tantangannya kurang menarik, terutama karena beberapa bahasa memiliki konversi berbasis basis arbitrer. Juga, saya tidak berpikir itu menangkap ide menghasilkan set yang tak terbatas daripada menanyakannya.
xnor
Bisakah Anda menjelaskan "menghasilkan objek yang tak terbatas"? Apakah itu berarti kita dapat misalnya mendorong setiap string ke stack (untuk bahasa stack) dan membiarkannya berjalan "selamanya", bahkan jika tidak ada output yang akan dihasilkan karena program tidak akan selesai?
Luis Mendo
@DonMuesli Apakah keluaran ke stack merupakan metode keluaran yang diterima untuk bahasa seperti itu? Dan, akankah stack hanya berisi string ini kapan saja?
xnor

Jawaban:

26

Python 2, 53 56

-3 setelah disadari yang yield xdapat digunakan sebagai ekspresi.

def f(s):yield'';[(yield w+c)for w in f(s)for c in s]
feersum
sumber
Satu byte lebih pendek, tapi dimulai pada 'aa'daripada di '': S=lambda s:(c+w for f in[str,S]for w in f(s)for c in s). Juga tidak berfungsi untuk input kosong.
orlp
20

Haskell, 24 byte

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

Menghasilkan daftar tanpa batas.

*Main> f "abc"
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa","caa","aba","bba","cba",…
Anders Kaseorg
sumber
Sayang sekali (:)<$>s<*>f sakan memberikan urutan yang salah. Ada f s="":(flip(:)<$>f s<*>s)tapi lebih lama.
xnor
Ya. Saya telah menemukan 23-byte f s=[]:(f s<**>map(:)s)kecuali yang <**>tidak ada Prelude.
Anders Kaseorg
11

JavaScript (ES6), 61 byte

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

Port generator Python @ feersum. Itu letperlu. Simpan 2 byte dengan menggunakan pemahaman array (gagal proposal ES7, tetapi berfungsi di Firefox 30-57):

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

Versi alternatif untuk 73 byte yang mengembalikan nelemen pertama yang dihasilkan oleh generator di atas:

(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)
Neil
sumber
JS punya generator? : 0000000
kucing
10

Mathematica, 32 31 Bytes

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

Edit:

CatsAreFluffy menghapus satu byte.

murphy
sumber
8

Perl, 39 37 35 byte

(Pertama menjelaskan versi yang lebih lama. Program yang lebih pendek baru di akhir)

Termasuk +3 untuk -alp

Jalankan dengan set karakter pada STDIN, mis perl -alp kleene.pl <<< "a b c"

kleene.pl (versi ini adalah 34 + 3 byte):

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

Tambahkan +2 untuk -F(drop implisit -ajika tidak ada spasi di antara karakter input, atau -6 (hanya @a=""sebelum }) jika kita sudah meletakkan koma di antara karakter pada STDIN

Penjelasan:

The -alppilihan membuat kode secara efektif:

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

Seperti yang Anda lihat <>di perl tidak hanya digunakan untuk readline, tetapi juga dapat melakukan globbing shell style (sebenarnya di perl kuno itu diimplementasikan dengan memanggil shell).

Misalnya <{a,b}{1,2}>akan diperluas ke"a1","a2","b1","b2"

Jadi, jika kita memiliki elemen di dalamnya, @Fkita hanya perlu menambahkan koma peralihan. Karakter inbetween default untuk interpolasi adalah space, yang disimpan dalam variabel khusus $". Jadi pengaturan $"untuk ,akan berubah "{@F}"menjadi {a,b}jika @F=qw(a b)(gumpalan diperluas sebagai string)

Sebenarnya saya benar-benar ingin loop dengan sesuatu seperti glob"{@F}"x$n++, tetapi saya terus mengalami masalah bahwa baris kosong pertama tidak dapat dihasilkan dan semua solusi yang saya temukan membuat kode terlalu lama.

Jadi bagian penting lain dari kode ini adalah bahwa jika Anda menggunakan foruntuk loop di atas array Anda benar-benar dapat mendorong elemen tambahan di dalamnya selama loop dan loop juga akan mengambil elemen-elemen baru ini. Jadi jika dalam loop kita misalnya pada elemen "ab", maka <{@F}$_>akan diperluas ke <{a,b}ab>mana dalam konteks daftar menjadi ("aab", "bab"). Jadi jika saya dorong ini @amaka senar diperpanjang ke kiri menjadi tersedia juga

Yang masih perlu saya lakukan adalah prime loop dengan string kosong. Itu dilakukan dengan menggunakan $#a = 0( ,dalam konteks numerik menjadi 0) yang menyebabkan elemen pertama dan satu-satunya @amenjadi undef yang akan berperilaku seperti ""ketika saya menggunakannya

Perbaikan

Bahkan dengan melakukan tes untuk penjelasan ini saya menemukan cara singkat untuk menggunakan gumpalan yang tumbuh yang benar menangani entri kosong pertama. Jalankan sebagai perl -ap kleene0.pl <<< "a b"(jadi tambahkan 2 byte untuk -ap)

kleene0.pl (versi ini adalah 33 + 2 byte):

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

Semua solusi ini akan membuat semakin banyak output dalam memori dan itu akan menyebabkan program gagal setelah beberapa waktu. Anda juga dapat menggunakan perl global untuk generasi malas dengan menggunakannya dalam konteks skalar, tetapi itu membuat program lebih panjang ....

Ton Hospel
sumber
Bisakah Anda jelaskan apa yang terjadi di sekitar <{@F}$_>:? Terima kasih!
andlrc
6

Pyth, 7

<s^LzQQ

Coba di sini

Ini menghitung produk kartesius dari input dengan setiap nomor dari 0..n-1, bergabung dengan mereka, dan kemudian hanya menyimpan yang pertama n. Ini akan habis waktu online untuk nomor atau string yang jauh lebih besar dari 3-4.

Atau, untuk mendapatkan hasil tak terbatas lihat jawaban Jakube .

FryAmTheEggman
sumber
5

Jelly, 8 6 bytes

⁷³p$Ȯ¿

This is a monadic link that accepts an alphabet and prints an infinite list of strings. Try it online!

How it works

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

Alternate version, 6 bytes (non-competing)

R’ḃL}ị

This is a dyadic link that accepts an alphabet and the desired number of strings as left and right arguments, respectively.

I consider this version non-competing, since it uses bijective base conversion, which has been implemented after this challenge had been sandboxed. Try it online!

How it works

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
sumber
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
sumber
Wow. Shorter and without builtins.
Morgan Thrapp
4

CJam, 16 10 bytes

Thanks to jimmy23013 for saving 6 bytes.

N{eam*_o}h

Input is one command-line argument per character. Output is one string on each line.

Try it online! (But kill it immediately...)

Explanation

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

Pyth, 7 bytes

.V0j^zb

Alternative to @fry. This program reads a string and keeps on printing strings until infinity.

Explanation:

.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

Alternatively the following will also work. A little bit more hacky though. 

u
M^zH7
Jakube
sumber
3

Haskell, 33 bytes

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

For exampe, k "xyz" is the infinite list ["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]

Lynn
sumber
3

MATL, 10 bytes

0cD`G@Z^DT

Try it online! But don't leave it running for long, to avoid large computational load on the server.

The program displays the strings dynamically, each string on a different line.

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
sumber
2

Python 3, 95

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

Why must itertools functions have such long names.

Morgan Thrapp
sumber
3
combinations_with_replacement is never worth it. I'm pretty sure it's shorter to use loops. Always.
mbomb007
2

Ruby, 65 60 bytes

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

Such long builtin names...

Doorknob
sumber
1
AFAIK You don't need the space before & and you can use p instead of puts.
Fund Monica's Lawsuit
@QPaysTaxes The space cannot be dropped, and p calls inspect on its arguments which would produce output like [] ["a","b"] ["aa", "ab", ...
Doorknob
I misunderstood your answer. I thought it was generating an infinite array and printing it. However, I'm fairly sure that on Array, to_s is aliased to inspect, so puts and p have the same output. ruby-doc.org/core-2.2.0/Array.html#method-i-to_s WRT the space: Did you check? Admittedly I'm not certain, but I'm fairly sure about it.
Fund Monica's Lawsuit
1

Pyke (commit 31), 10 9 bytes

=blR.fbtp

Explanation:

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

Scala, 69

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

Lazy streams are quite nice for this kind of thing.

Joe K
sumber
1

Japt, 50 40 34 28 bytes

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

Input is "string", number of items. Output is sorted by length, then reverse alphabet order. Test it online!

How it works

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.

This version takes a while if you want to do any more than 100 items. If you want a faster version, try this 32-byte one:

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

Cinnamon Gum, 6 bytes

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

Non-competing because Cinnamon Gum was made after this challenge.

Try it online (TIO limits output).

Explanation

The h puts Cinnamon Gum in format and generate mode. The rest of the string decompresses to [%s]*. The %s is then replaced with the input, and a generator is created that outputs all possible strings matching the regex.

a spaghetto
sumber
1

05AB1E, 9 bytes

g<∞*εÅв¦J

Try it 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
sumber
0

Python, 55 bytes

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

This is longer than feersum's 53-byte solution, but it illustrates a different method with printed output. The list l is updated while it is iterated over, by appending every one-character suffix of each string that is read.

It's equally long to use map:

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

The same length can be done in Python 3, losing a char for print(), and saving one by input unpacking.

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

Zsh, 31 bytes

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

Try it online!

Print the array, then zip on the arguments before recursing. Despite including the function name, this is one byte shorter than the iterative version:

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