Вывести все строки

34

Учитывая набор букв, выведите все строки, составленные из этих букв. (Это звезда Клини из набора.) Например, для {'a','b'}строк:

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

Входные данные: непустая коллекция различных букв a..z. Это могут быть символы или односимвольные строки.

Вывод: все строки в этих письмах в любом порядке, без повторов. Вы можете использовать списки символов в качестве строк.

Это бесконечный список, поэтому вы можете вывести его:

  • Бегать вечно, писать все больше и больше строк. Эти строки могут быть записаны в любом плоском разделенном формате, что означает, что вы можете сказать, где заканчивается каждая строка, но строки не подразделяются на группы.
  • Взятие числа в nкачестве ввода и вывод первых nстрок в любом плоском формате
  • Выдача каждой строки по очереди из объекта генератора
  • Создание бесконечного объекта

Убедитесь, что ваш метод в конечном итоге генерирует каждую строку в выводе, так как можно создать бесконечное количество строк из набора, не доходя до некоторых строк.

Вы не можете вывести его по

  • Производится nзаданная строкаn
  • Обеспечение оракула членства, который решает, принадлежит ли данная строка к набору

Встроенные модули разрешены, но я прошу избирателей обратить внимание на ответы, которые сами реализуют операцию, а не на встроенные.

Показать фрагмент кода

code-golf string XNOR
источник
@Cyoce Не знаю, что ты имеешь в виду. Я уточнил, что строки должны быть разделены, чтобы вы могли отличить пустую строку от нуля.
xnor
Пожалуйста, объясните, почему «создание N-й строки с учетом N» не допускается.
CalculatorFeline
4
@CatsAreFluffy Это был судебный звонок. Я думаю, что создание N-й строки было бы слишком простым по сравнению с альтернативами и сделало бы задачу менее интересной, особенно потому, что в некоторых языках было встроено произвольное базовое преобразование. Кроме того, я не думал, что это захватило идею генерирования бесконечного множества, а не запрашивая его.
xnor
Можете ли вы объяснить «производство бесконечного объекта»? Означает ли это, что мы можем, например, поместить каждую строку в стек (для языков стека) и позволить ей работать «вечно», даже если не будет получен вывод, потому что программа не завершит работу?
Луис Мендо
@DonMuesli Является ли вывод в стек приемлемым методом вывода для таких языков? И будет ли стек содержать только эти строки в любой момент времени?
xnor

Ответы:

26

Python 2, 53 56

-3 после осознания того, что yield xможно использовать как выражение.

def f(s):yield'';[(yield w+c)for w in f(s)for c in s]
feersum
источник
Один байт короче, но начинается с , 'aa'а не на '': S=lambda s:(c+w for f in[str,S]for w in f(s)for c in s). Также не работает для пустого ввода.
orlp
20

Haskell, 24 байта

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

Создает бесконечный список.

*Main> f "abc"
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa","caa","aba","bba","cba",…
Андерс Касеорг
источник
Жаль, (:)<$>s<*>f sчто дал бы неправильный порядок. Там, f s="":(flip(:)<$>f s<*>s)но это дольше.
xnor
Да. Я нашел 23 байта, f s=[]:(f s<**>map(:)s)кроме того, что <**>нет в Prelude.
Андерс Касеорг
11

JavaScript (ES6), 61 байт

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

Порт генератора @ feersum Python. Это letнеобходимо. Сохраните 2 байта, используя понимание массива (предложение ES7 провалилось, но работает в Firefox 30-57):

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

Альтернативная версия для 73 байтов, которая возвращает первые nэлементы, полученные вышеупомянутым генератором:

(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)
Нил
источник
У JS есть генераторы? : 0000000
кот
10

Mathematica, 32 31 байт

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

Редактировать:

CatsAreFluffy соскоблил один байт.

Murphy
источник
8

Perl, 39 37 35 байт

(Сначала описывает более старую версию. Новая более короткая программа находится в конце)

Включает +3 для -alp

Запуск с набором символов на STDIN, например perl -alp kleene.pl <<< "a b c"

kleene.pl (эта версия составляет 34 + 3 байта):

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

Добавьте +2 для -F(неявное удаление, -aесли между входными символами нет пробелов, или -6 (только @a=""перед }), если мы уже ставим запятые между символами в STDIN

Объяснение:

Эти -alpпараметры эффективно сделать код:

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

Как вы можете видеть, <>perl не только используется для readline, но также может выполнять глобализацию в стиле оболочки (фактически, в древних perl это было реализовано с помощью вызова оболочки).

Например <{a,b}{1,2}>, расширится до"a1","a2","b1","b2"

Поэтому, если у нас есть элементы, @Fнам просто нужно добавить запятые между ними. Символ по умолчанию для интерполяции - это пробел, который хранится в специальной переменной $". Таким образом , установив , $"чтобы ,превратится "{@F}"в {a,b}случае @F=qw(a b)(шарики расширения в виде строк)

На самом деле мне бы очень хотелось выполнить цикл с чем-то вроде этого glob"{@F}"x$n++, но я продолжал сталкиваться с проблемой, что первая пустая строка не генерируется, и все найденные обходные пути сделали код слишком длинным.

Таким образом, другая важная часть этого кода состоит в том, что если вы используете forцикл для массива, вы можете фактически вставить в него дополнительные элементы во время цикла, и цикл также получит эти новые элементы. Так что если в цикле мы находимся, например, в элементе "ab", то <{@F}$_>расширимся до того, <{a,b}ab>что в контексте списка становится ("aab", "bab"). Так что, если я нажимаю на них, @aто становятся доступными также строки, расширенные слева.

Все, что мне еще нужно сделать, это заправить цикл пустой строкой. Это делается с помощью $#a = 0( ,в числовом контексте становится 0), что заставляет первый и единственный элемент @aстать undef, который будет вести себя как, ""когда я его использую

улучшение

Фактически, выполняя тесты для этого объяснения, я нашел короткий способ использовать растущий глобус, который правильно обрабатывает первую пустую запись. Запускать как perl -ap kleene0.pl <<< "a b"(так добавьте 2 байта для -ap)

kleene0.pl (эта версия составляет 33 + 2 байта):

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

Все эти решения будут сохранять все больше и больше выходных данных в памяти, что приведет к сбою программы через некоторое время. Вы также можете использовать Perl Globs для отложенной генерации, используя их в скалярном контексте, но это делает программы длиннее ...

Тон Хоспел
источник
Можете ли вы объяснить , что происходит вокруг: <{@F}$_>? Благодарность!
andlrc
6

Пиф, 7

<s^LzQQ

Попробуй здесь

Это вычисляет декартово произведение входных данных с каждым числом 0..n-1, соединяет их, а затем сохраняет только первое n. Это будет время ожидания онлайн для чисел или строк, которые намного больше, чем 3-4.

В качестве альтернативы, чтобы получить бесконечный результат, посмотрите на ответ Якуба .

FryAmTheEggman
источник
5

Желе, 8 6 байт

⁷³p$Ȯ¿

Это монадическая ссылка, которая принимает алфавит и печатает бесконечный список строк. Попробуйте онлайн!

Как это работает

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

Альтернативная версия, 6 байт (не конкурирует)

R’ḃL}ị

Это диадическая ссылка, которая принимает алфавит и желаемое количество строк в качестве левого и правого аргументов соответственно.

Я считаю эту версию неконкурентной, поскольку в ней используется биективное базовое преобразование, которое было реализовано после того, как эта задача была помещена в «песочницу». Попробуйте онлайн!

Как это работает

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.
Деннис
источник
4

Python 2, 89 84 83 байта

x,n=input()
l=len(x)
for i in range(n):
 s=''
 while i:i-=1;s+=x[i%l];i/=l
 print s
Деннис
источник
Вау. Короче и без встроенных.
Морган Трепп
4

CJam, 16 10 байт

Спасибо jimmy23013 за сохранение 6 байтов.

N{eam*_o}h

Ввод - это один аргумент командной строки на символ. Выход - одна строка в каждой строке.

Попробуйте онлайн! (Но убей это немедленно ...)

объяснение

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
Мартин Эндер
источник
3

Pyth, 7 байт

.V0j^zb

Альтернатива @fry. Эта программа читает строку и продолжает печатать строки до бесконечности.

Объяснение:

.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

В качестве альтернативы следующее также будет работать. Немного более хакерский, хотя.

u
M^zH7
Jakube
источник
3

Haskell, 33 байта

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

Например, k "xyz"это бесконечный список["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]

Линн
источник
3

MATL , 10 байт

0cD`G@Z^DT

Попробуйте онлайн! Но не оставляйте его работать долго, чтобы избежать большой вычислительной нагрузки на сервер.

Программа отображает строки динамически, каждая строка в отдельной строке.

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
Луис Мендо
источник
2

Питон 3, 95

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

Почему функции itertools должны иметь такие длинные имена.

Морган Трепп
источник
3
combinations_with_replacementэто никогда не стоит Я уверен, что использовать петли короче. Всегда.
mbomb007
2

Рубин, 65 60 байт

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

Такие длинные встроенные имена ...

Дверная ручка
источник
1
AFAIK. Вам не нужно места перед &, и вы можете использовать p вместо пут.
Фонд Моника иск
@QPaysTaxes Пространство не может быть отброшено, и pвызывает inspectего аргументы, которые будут производить вывод, как[] ["a","b"] ["aa", "ab", ...
Doorknob
Я неправильно понял ваш ответ. Я думал, что это генерирует бесконечный массив и печатает его. Тем не менее, я вполне уверен, что в массиве to_s имеет псевдоним для проверки, поэтому put и p имеют одинаковый вывод. ruby-doc.org/core-2.2.0/Array.html#method-i-to_s WRT пространство: вы проверяли? По общему признанию я не уверен, но я довольно уверен в этом.
Фонд Моники судебный процесс
1

Пайк (коммит 31), 10 9 байт

=blR.fbtp

Объяснение:

=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(^)
синий
источник
1

Скала, 69

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

Ленивые потоки довольно хороши для такого рода вещей.

Джо К
источник
1

Japt, 50 40 34 28 байт

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

Вход есть "string", number of items. Вывод сортируется по длине, затем в обратном алфавитном порядке. Проверьте это онлайн!

Как это работает

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.

Эта версия занимает некоторое время, если вы хотите сделать более 100 предметов. Если вы хотите более быструю версию, попробуйте эту 32-байтовую версию :

V*2 o ms1+Ul)f@!Xf'0î£UgXnH}ïV
ETHproductions
источник
1

Корица, 6 байт

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

Не конкурирует, потому что Корица Gum была сделана после этого испытания.

Попробуйте онлайн (TIO ограничивает вывод).

объяснение

The hпомещает Cinnamon Gum в формат и режим генерации . Остальная часть строки распаковывается в [%s]*. Затем %sон заменяется вводом, и создается генератор, который выводит все возможные строки, соответствующие регулярному выражению.

спагетто
источник
1

05AB1E , 9 байтов

g<∞*εÅв¦J

Попробуйте онлайн!

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
источник
0

Python, 55 байт

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

Это длиннее 53-байтового решения feersum , но оно иллюстрирует другой метод с выводом на печать. Список lобновляется, пока он повторяется, добавляя каждый односимвольный суффикс каждой читаемой строки.

Это одинаково долго использовать map:

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

Такую же длину можно сделать в Python 3, потеряв символ для print()и сохранив его путем распаковки ввода.

s,*l=input(),''
for x in l:print(x);l+=[x+c for c in s]
XNOR
источник
0

Zsh , 31 байт

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

Попробуйте онлайн!

Распечатайте массив, а затем скопируйте аргументы перед повторением. Несмотря на включение имени функции, это на один байт короче, чем итерационная версия:

for ((;;))<<<${(F)a}&&a=($^a$^@)
GammaFunction
источник