Я недавно видел этот вопрос на stackoverflow. Это отличный вопрос, но есть одна фатальная проблема с этим вопросом. Они просят лучшего способа сделать это. Например, самый легкий для чтения, самый идиоматичный, самый красивый и т. Д. Разве они не знают, что это не главное? Вы должны спросить о том, как сделать это с наименьшим количеством байтов кода!
Поскольку я сомневаюсь, что этот вопрос будет оценен по stackoverflow, я решил задать его здесь.
Соревнование
Вы должны написать максимально короткую программу или функцию, которая генерирует все возможные способы чередования любых двух произвольных строк. Например, если две строки - это 'ab'
и 'cd'
, вывод:
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']
Как видите, a
всегда раньше b
и c
всегда раньше d
.
IO может быть в любом разумном формате. Используйте этот код Python для проверки, чтобы проверить ваш вывод. (кредит: JeD )
def shuffle(s,t):
if s=="":
return [t]
elif t=="":
return [s]
else:
leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
leftShuffle.extend(rightShuffle)
return leftShuffle
Образец ввода-вывода:
shuffle("$", "1234"):
['$1234', '1$234', '12$34', '123$4', '1234$']
shuffle("az", "by"):
['azby', 'abzy', 'abyz', 'bazy', 'bayz', 'byaz']
shuffle("code", "golf"):
['codegolf', 'codgeolf', 'codgoelf', 'codgolef', 'codgolfe', 'cogdeolf', 'cogdoelf',
'cogdolef', 'cogdolfe', 'cogodelf', 'cogodlef', 'cogodlfe', 'cogoldef', 'cogoldfe',
'cogolfde', 'cgodeolf', 'cgodoelf', 'cgodolef', 'cgodolfe', 'cgoodelf', 'cgoodlef',
'cgoodlfe', 'cgooldef', 'cgooldfe', 'cgoolfde', 'cgoodelf', 'cgoodlef', 'cgoodlfe',
'cgooldef', 'cgooldfe', 'cgoolfde', 'cgolodef', 'cgolodfe', 'cgolofde', 'cgolfode',
'gcodeolf', 'gcodoelf', 'gcodolef', 'gcodolfe', 'gcoodelf', 'gcoodlef', 'gcoodlfe',
'gcooldef', 'gcooldfe', 'gcoolfde', 'gcoodelf', 'gcoodlef', 'gcoodlfe', 'gcooldef',
'gcooldfe', 'gcoolfde', 'gcolodef', 'gcolodfe', 'gcolofde', 'gcolfode', 'gocodelf',
'gocodlef', 'gocodlfe', 'gocoldef', 'gocoldfe', 'gocolfde', 'goclodef', 'goclodfe',
'goclofde', 'goclfode', 'golcodef', 'golcodfe', 'golcofde', 'golcfode', 'golfcode']
Как обычно, применяются стандартные лазейки, и выигрывает самый короткий ответ в байтах. Поскольку вопрос изначально был о питоне, я бы хотел увидеть самый короткий ответ по питону. (И нет, пит - это не питон). Тем не менее, ответы на любом языке приветствуются.
источник
Ответы:
Пиф, 26
Попробуй здесь
Это очень базовая реализация данной рекурсивной формулы. Он определяет функцию,
g
которая выполняет требуемую задачу. Ссылка представляет собой измененную программу, которая для удобства чтения читает строки из новой строки STDIN. Для вызова функции сделайтеg<string1><string2>
.Расширение:
Эти два рекурсивных вызова очень похожи, но я больше не смог найти способ сыграть в них в гольф.
источник
Haskell,
5348 байтовОпределяет функцию,
%
для которойa%b
со строкамиa,b
выдает список строк.Учитывая две строки, мы выбираем одну из двух, чтобы взять первый символ. Затем мы возвращаемся к оставшейся части двух строк, добавляя этот символ к каждому результату.
Когда одна из строк пуста, единственным возможным результатом является другая строка.
""%""=[""]
также будет достаточно, но это дольше.53 байта:
Определяет функцию,
%
для которойa%d
со строкамиa,d
выдает список строк.Функция определяется рекурсивно. Если мы берем символ из первой строки, то он должен быть добавлен перед каждым результатом рекурсивного вызова в оставшейся части первой строки со второй строкой. Симметрично для другой строки.
Для базового случая, если одна из строк пуста, результатом является одноэлементный список их конкатенации. Это короче, чем два случая, когда каждая строка пуста.
источник
""%""=[""]
.Хаскелл, 47
%
это оператор, который решает эту проблему.#
является оператором, который берет два списка и находит все способы их чередования, так что первый символ берется из первой строки (с крайним регистром - если первый список пуст, то результат является пустым списком) путем возврата к%
,затем
%
работает, просто применяя#
дважды.Изменить: в предыдущей версии была ошибка, в которой
""%""
вернулся["",""]
, поэтому я исправил. Это было исправлено путем добавления базового варианта к%
, который затем позволял удалить базовый вариант такой же длины#
(что на самом деле не имело особого смысла).источник
(#) :: [a]->[a]->[[a]]
значит,a::[a]
и результат должен быть[[a]]
Python 2, 71 байт
Пример выполнения:
Учитывая две строки,
x,y
мы можем взять первый символx
и добавить его к каждому результату рекурсивного вызова, пропустив егоf(x[1:],y)
. Или мы можем сделать то же самое сx
иy
переключил. Взявx,y
за входp
или за его обращение `p [:: - 1], мы получим обе возможности.Чтобы избежать взятия из пустой строки
x
, мы логически закоротим сx and
. Если обе строки пусты, ни одна строка не может быть,x
и мы получаем и пустой список возможностей, которые мы фиксируемor
в правильном базовом случае['']
.Аналогичная генеративная стратегия в Python 3 (73 байта):
источник
Python, 80
Как и просили, вот ответ Python:
Спасибо Sp3000 за то, что съели 4 байта :)
источник
CJam, 38
Попробуйте онлайн
Динамическое программирование (с использованием запомненной рекурсии).
Объяснение:
источник
CJam, 32 байта
Проверьте это здесь.
Это кажется действительно пригодным для игры в гольф, но до сих пор я нашел только 4 альтернативных решения с одинаковым количеством байтов:
Основная идея состоит в том, чтобы сгенерировать все перестановки
0
s и1
s, соответствующие какой строке взять из каждого символа в результате. Это все до и в том числеe!
. Остальные просто вытаскивают персонажей в указанном порядке из двух строк.источник
e*
и.*
который повторяет каждый элемент по разным количеством. ;) (Т.е. оператор делать:a.*:~
я полагаю.e*
Можно было бы использовать для этого , так как он в настоящее время ошибок , если даны два списка).JavaScript (Firefox 30-57),
888481 байтИзменить: Сохранено 4 байта путем улучшения моего условия завершения. Сохранено 3 байта благодаря @ edc65.
источник
f=(a,b,z=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>z(a,b).concat(z(b,a))
v
в качестве условия, но мне никогда не приходило в голову использоватьv[1]
.Брахилог , 8 байт
Попробуйте онлайн!
Принимает input как список из двух строк через входную переменную и генерирует все возможные чередования через выходную переменную. Поскольку контрольные примеры, по-видимому, допускают дублирующиеся чередования, когда есть общие буквы, я не позаботился о том, чтобы их избежать, но это создает намного больше дубликатов, а не только с общими буквами. (Если это не разрешено, но общие дубликаты букв не нужны, просто добавьте три байта для переноса
{}ᵘ
для вывода в виде списка без дубликатов.)По сути, это генерирует каждое разделение обеих строк, а затем перемежает их обычным детерминированным способом в любом порядке. Дополнительное дублирование чередования происходит из-за пар разделов, где разница между длиной первого и длиной второго имеет некоторое значение, отличное от 0 или 1, так что один из них имеет фрагменты, которые соединяются друг с другом в конце. Итак, чтобы получить выходные данные с теми же кратностями, что и для выходных данных примера:
Брахилог , 17 байт
Попробуйте онлайн!
Дополнительный код
{lᵐ-ℕ<2&}
не работает с любой парой разделов, в которой сделаны какие-либо посторонние разделы. (Я изменил заголовок на TIO для печати с кавычками для облегчения проверки вывода в оболочке Python.)источник
MATL ,
3430 байтЗдесь используется идея из этого ответа : если длина строк равна
m
иn
, перечислите всеm+n
битовые комбинации сm
установленными битами. Один из способов сделать это перечисление: генерировать все перестановки вектора сm
единицами иn
нулями, а затем удалять дубликаты.Попробуйте онлайн!
объяснение
источник
Рубин, 83 байта
Рекурсивная функция, которая возвращает
[a+b]
если любая из этих строк пуста. В противном случае он возвращает список строк,a[0] + every string in v[a[1..-1],b]
добавленных в список строкb[0] + every string in v[a,b[1..-1]]
источник
Пакет,
154152 байтаисточник