Niedawno widziałem to pytanie przy przepełnieniu stosu. To świetne pytanie, ale jest jeden poważny problem z pytaniem. Pytają o najlepszy sposób, aby to zrobić. Np. Najłatwiejszy do odczytania, najbardziej idiomatyczny, schludny itp. Czy oni nie wiedzą, że to nie ma znaczenia? Powinieneś zapytać, jak to zrobić, używając jak najmniej bajtów kodu!

Ponieważ wątpię, czy to pytanie zostanie docenione przy przepływie stosów, postanowiłem zadać je tutaj.

Wyzwanie

Musisz napisać możliwie najkrótszy program lub funkcję, która generuje wszystkie możliwe sposoby przeplatania dowolnych dwóch dowolnych ciągów. Na przykład, jeśli dwa ciągi są 'ab'i 'cd', wynikiem jest:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

Jak widać, ajest zawsze wcześniej bi czawsze jest wcześniej d.

IO może mieć dowolny rozsądny format. Użyj tego kodu python, aby sprawdzić, aby sprawdzić wyniki. (kredyt: 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

Próbka IO:

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']

Jak zwykle obowiązują standardowe luki i wygrywa najkrótsza odpowiedź w bajtach. Ponieważ pytanie pierwotnie dotyczyło Pythona, chciałbym zobaczyć najkrótszą odpowiedź na python. (I nie, pyth to nie python). Zachęca się jednak do odpowiedzi w dowolnym języku.

Pyth, 26

M?G?H++LhGgtGH+LhHgGtH]G]H

Wypróbuj tutaj

Jest to bardzo podstawowa implementacja danej formuły rekurencyjnej. Definiuje funkcję, gktóra wykonuje wymagane zadanie. Link jest zmodyfikowanym programem, który odczytuje ciągi znaków oddzielone STDIN oddzielone, dla wygody. Aby wywołać funkcję, wykonaj g<string1><string2>.

Ekspansja:

M                ##  Define a function g taking two arguments: G and H
 ?G?H ... ]G]H   ##  Two ternaries: if G is empty return a list containing H
                 ##  if H is empty return a list containing G
   +             ##  otherwise return these next two lists joined together
   +LhGgtGH      ##  the first letter of G added to each result of a recursive call to g
                 ##  with G missing its first character and H
   +LhHgGtH      ##  the same as above but with G and H swapped

Te dwa rekurencyjne połączenia są bardzo podobne, ale nie byłem w stanie znaleźć sposobu na ich grę w golfa.

Haskell, 53 48 bajtów

a%""=[a]
a%b=[x:t|(x:y,z)<-[(a,b),(b,a)],t<-y%z]

Definiuje funkcję, %dla której za a%bpomocą łańcuchów a,bpodano listę łańcuchów.

Biorąc pod uwagę dwa ciągi, wybieramy jeden z dwóch, z którego bierze się pierwszy znak. Następnie wykonujemy rekurencję na pozostałych dwóch ciągach, przygotowując ten znak do każdego wyniku.

Gdy jeden z ciągów jest pusty, jedynym możliwym wynikiem jest drugi ciąg. ""%""=[""]wystarczyłoby, ale jest dłużej.

53 bajty:

a@(b:c)%d@(e:f)=((b:)<$>c%d)++((e:)<$>a%f)
a%d=[a++d]

Definiuje funkcję, %dla której za a%dpomocą łańcuchów a,dpodano listę łańcuchów.

Funkcja jest zdefiniowana rekurencyjnie. Jeśli weźmiemy znak z pierwszego łańcucha, to musi on być poprzedzony każdym wynikiem wywołania rekurencyjnego na pozostałym ciągu pierwszego łańcucha z drugim łańcuchem. Symetrycznie dla drugiego ciągu.

W przypadku podstawowym, jeśli jeden z ciągów jest pusty, wynikiem jest lista jednoelementowa ich konkatenacji. Jest to mniej niż dwa przypadki dla każdego ciągu pustego.

Haskell, 47 lat

(x:s)#b=(x:)<$>s%b
a#b=[]
[]%b=[b]
a%b=a#b++b#a

% jest operatorem, który rozwiązuje to wyzwanie.

#jest operatorem, który pobiera dwie listy i znajduje wszystkie sposoby ich przeplatania w taki sposób, że pierwszy znak pochodzi z pierwszego łańcucha (z przypadkiem krawędzi - jeśli pierwsza lista jest pusta, to wynikiem jest pusta lista) poprzez rekurencję do %.

następnie %działa tylko #dwukrotnie.

Edycja: poprzednia wersja miała błąd, w którym ""%""wróciła ["",""], więc naprawiłem to. Zostało to naprawione przez dodanie skrzynki podstawowej %, co pozwoliło następnie usunąć skrzynkę podstawową o tej samej długości #(co tak naprawdę nie miało większego sensu).

Python 2, 71 bajtów

f=lambda*p:[x[0]+t for x,y in p,p[::-1]for t in x and f(x[1:],y)]or['']

Przykładowy przebieg:

>> f('ab','AB')
['abAB', 'aABb', 'aAbB', 'ABab', 'AabB', 'AaBb']

Biorąc pod uwagę dwa ciągi znaków x,y, możemy wziąć pierwszy znak xi dołączyć go do każdego wyniku wywołania rekurencyjnego, gdy go brakuje f(x[1:],y). Albo możemy zrobić to samo z xi ywłączony. Przyjmując x,yjako wejście plub jego odwrócenie `p [:: - 1], otrzymujemy obie możliwości.

Aby uniknąć pobrania z pustego ciągu x, logicznie zwarliśmy się z x and. Jeśli oba ciągi są puste, żaden ciąg nie może być, xa my otrzymujemy i opróżniamy listę możliwości, które naprawiamy orw poprawnej podstawowej skrzynce [''].

Podobna strategia generatywna w Pythonie 3 (73 bajty):

f=lambda p,s='':[f((x[1:],y),s+x[0])for x,y in[p,p[::-1]]if x]or print(s)

Python, 80

Zgodnie z prośbą, oto odpowiedź python:

f=lambda a,b,c='':[c+x for x in[a+b][a>''<b:]or f(a[1:],b,a[0])+f(a,b[1:],b[0])]

Dzięki Sp3000 za zjedzenie 4 bajtów :)

CJam, 38 lat

q~L{_2$e&{_2$(\@jf+@@(@@jf++}{+a}?}2jp

Wypróbuj online

Programowanie dynamiczne (z wykorzystaniem zapamiętanej rekurencji).

Wyjaśnienie:

q~         read and evaluate the input (2 strings)
L{…}2j     calculate with memoized recursion with no initial cache and 2 arguments
  _2$      copy the 2 strings
  e&{…}    if they are both non-empty
    _2$    copy the strings again (they're in reverse order)
    (      take out the first character of the first string
    \@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    @@     bring the other copy of the strings on top (in order)
    (      take out the first character of the second string
    @@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    +      concatenate the 2 sets of results
  {…}      else
    +      concatenate the 2 strings (at least one is empty)
    a      put the result in an array
  ?        end if
p          pretty-print the results for the input strings

CJam, 32 bajty

qN/_:,eeWf%e~e!\f{\{_2$=(ot}/No}

Sprawdź to tutaj.

To naprawdę gra w golfa, ale do tej pory znalazłem tylko 4 alternatywne rozwiązania, z których wszystkie mają tę samą liczbę bajtów:

qN/_ee{),*~}%e!\f{\{_2$=(ot}/No}
l_:!l_0f>@+])e!\f{\{_2$=(ot}/No}
ll__3$:!+.=])e!\f{\{_2$=(ot}/No}
qN/[_:,2,]ze~e!\f{\{_2$=(ot}/No} (found by Sp3000)

Podstawową ideą jest wygenerowanie wszystkich permutacji 0si i 1s odpowiadających ciągowi znaków, z którego ma wynikać każdy znak. To wszystko do włącznie e!. Reszta po prostu wyciąga znaki w tej kolejności z dwóch ciągów.

JavaScript (Firefox 30-57), 88 84 81 bajtów

(s,t,g=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>[...g(s,t),...g(t,s)]

Edycja: Zapisano 4 bajty, poprawiając mój warunek zakończenia. Zaoszczędzono 3 bajty dzięki @ edc65.

Brachylog , 8 bajtów

p~cᵐz₁cc

Wypróbuj online!

Pobiera dane wejściowe jako listę dwóch łańcuchów poprzez zmienną wejściową i generuje wszystkie możliwe przeploty poprzez zmienną wyjściową. Ponieważ przypadki testowe wydają się zezwalać na duplikaty przeplotów w przypadku wspólnych liter, nie starałem się ich unikać, ale generuje to o wiele więcej duplikatów, a nie tylko wspólnych liter. (Jeśli nie jest to dozwolone, ale duplikaty udostępnionych liter nie są konieczne, po prostu dodaj trzy bajty, aby zawinąć w {}ᵘcelu uzyskania jako listy bez duplikatów.)

p           A permutation of
            the input variable
   ᵐ        with each element
 ~c         arbitrarily partitioned,
    z       zipped
     ₁      without cycling,
      cc    and concatenated twice
            is the output variable.

Zasadniczo generuje to każdą partycję obu łańcuchów, a następnie przeplata je w normalny deterministyczny sposób w dowolnej kolejności. Dodatkowe duplikaty przeplatania są spowodowane parami podziału, w których różnica między długością pierwszego i długością drugiego ma pewną wartość inną niż 0 lub 1, tak że jeden z nich ma fragmenty, które na końcu łączą się ze sobą. Tak więc, aby uzyskać dane wyjściowe o takich samych krotnościach jak dane wyjściowe próbki:

Brachylog , 17 bajtów

p~cᵐ{lᵐ-ℕ<2&}z₁cc

Wypróbuj online!

Dodatkowy kod {lᵐ-ℕ<2&}nie działa na żadnej parze partycji, w której są tworzone podziały zewnętrzne. (Zmieniłem nagłówek w TIO, aby drukować z cudzysłowami, aby ułatwić sprawdzanie wyników w powłoce Pythona.)

MATL , 34 30 bajtów

h1Mgw~hY@Xu!ttYs*w~tYs1Gn+*+!)

Wykorzystuje to pomysł z tej odpowiedzi : jeśli długości ciągów są mi n, wylicz wszystkie m+nwzorce mbitów z ustawionymi bitami. Jednym ze sposobów wykonania tego wyliczenia jest: wygenerowanie wszystkich permutacji wektora za pomocą zer i mjedynek, na następnie usunięcie duplikatów.

Wypróbuj online!

Wyjaśnienie

h     % implicitly input the two strings of lengths m and n. Concatenate
1M    % push the two strings again
g     % convert the second strings into ones
w~    % swap. Convert the second string into zeros
h     % concatenate: vector of zeros and ones
Y@    % 2D array with all permutations of that vector, each on a row
Xu    % remove duplicate rows
!     % transpose
ttYs  % duplicate twice. Cumulative sum along each column
*     % element-wise product. Produces, in each column, indices for
      % elements of the first string; 1, 2,...,m. The rest are 0
w~    % swap, negate
tYs   % duplicate. Cumulative sum along each column
1Gn+  % add length of first input
*     % element-wise product. Produces, in each column, indices for
      % elements of the second string: m+1,...,m+n. The rest are 0
+     % add. This gives indices into the concatenated string created initially
!     % transpose back
)     % index into concatenated string. Implicitly display

Rubinowy, 83 bajty

Funkcja rekurencyjna, która zwraca, [a+b]jeśli którykolwiek z tych ciągów jest pusty. W przeciwnym razie zwraca listę ciągów a[0] + every string in v[a[1..-1],b]dodanych do listy ciągówb[0] + every string in v[a,b[1..-1]]

v=->a,b{a[0]&&b[0]?v[a[1..-1],b].map{|i|a[0]+i}+v[a,b[1..-1]].map{|i|b[0]+i}:[a+b]}

Partia, 154 152 bajtów

@if "%~1%~2"=="" echo %3
@set t=%~1
@if not "%t%"=="" call %0 "%t:~1%" "%~2" %3%t:~,1%
@set t=%~2
@if not "%t%"=="" call %0 "%~1" "%t:~1%" %3%t:~,1%