Ich habe diese Frage kürzlich beim Stackoverflow gesehen. Es ist eine großartige Frage, aber es gibt ein schwerwiegendes Problem mit der Frage. Sie fragen nach dem besten Weg, dies zu tun. ZB am einfachsten zu lesen, am idiomatischsten, am saubersten usw. Wissen sie nicht, dass es nicht darauf ankommt? Sie sollten sich fragen, wie Sie das mit den wenigsten Bytes Code machen sollen!

Da ich bezweifle, dass diese Frage beim Stackoverflow beantwortet wird, habe ich mich entschlossen, sie hier zu stellen.

Die Herausforderung

Sie müssen das kürzestmögliche Programm oder die kürzestmögliche Funktion schreiben, die alle möglichen Möglichkeiten zur Verschachtelung von zwei beliebigen Zeichenfolgen generiert. Wenn zum Beispiel die beiden Zeichenfolgen 'ab'und sind 'cd', lautet die Ausgabe:

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

Wie Sie sehen, aist immer vor bund cist immer vor d.

IO kann in jedem vernünftigen Format vorliegen. Verwenden Sie diesen Python-Code, um Ihre Ausgabe zu überprüfen. (Kredit: 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

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

Wie üblich gelten Standardlücken, und die kürzeste Antwort in Bytes gewinnt. Da es sich ursprünglich um Python handelte, würde ich gerne die kürzeste Python-Antwort sehen. (Und nein, Python ist nicht Python). Antworten in jeder Sprache sind jedoch erwünscht.

Pyth, 26

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

Probieren Sie es hier aus

Dies ist eine sehr grundlegende Implementierung der angegebenen rekursiven Formel. Es definiert eine Funktion g, die die erforderliche Aufgabe ausführt. Der Link ist ein modifiziertes Programm, das die Zeichenfolgen getrennt von STDIN-Zeilenumbrüchen liest, um dies zu vereinfachen. Um die Funktion aufzurufen, gehen Sie wie folgt vor g<string1><string2>.

Erweiterung:

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

Die beiden rekursiven Aufrufe sind sich sehr ähnlich, aber ich habe keinen Weg mehr gefunden, sie zu golfen.

Haskell, 53 48 Bytes

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

Definiert eine Funktion, %für die a%bmit Zeichenfolgen a,beine Liste von Zeichenfolgen erstellt wird.

Bei zwei gegebenen Zeichenfolgen wählen wir eine der beiden Zeichen aus, aus denen das erste Zeichen entnommen werden soll. Wir werden dann auf den Rest von zwei Zeichenketten zurückgreifen und jedem Ergebnis dieses Zeichen voranstellen.

Wenn einer der Strings leer ist, ist das einzig mögliche Ergebnis der andere String. ""%""=[""]würde auch genügen, ist aber länger.

53 Bytes:

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

Definiert eine Funktion, %für die a%dmit Zeichenfolgen a,deine Liste von Zeichenfolgen erstellt wird.

Die Funktion ist rekursiv definiert. Wenn wir ein Zeichen aus der ersten Zeichenfolge nehmen, muss es vor jedem Ergebnis des rekursiven Aufrufs auf den verbleibenden Teil der ersten Zeichenfolge mit der zweiten Zeichenfolge eingefügt werden. Symmetrisch für die andere Saite.

Wenn im Basisfall eine der Zeichenfolgen leer ist, ist das Ergebnis eine Einzelelementliste ihrer Verkettung. Dies ist kürzer als zwei Fälle für jede leere Zeichenfolge.

Haskell, 47

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

% ist der Betreiber, der diese Herausforderung löst.

#ist ein Operator, der zwei Listen aufnimmt und alle Möglichkeiten findet, sie so zu verschachteln, dass das erste Zeichen aus der ersten Zeichenfolge stammt (mit einem Kantenfall - wenn die erste Liste leer ist, ist das Ergebnis eine leere Liste), indem er rekursiv zu %.

Dann %funktioniert es, indem Sie es einfach #zweimal anwenden .

Bearbeiten: Die vorherige Version hatte einen Fehler, der ""%""zurückkehrte ["",""], also habe ich ihn behoben. Es wurde behoben, indem ein Basisfall hinzugefügt wurde %, aus dem dann ein Basisfall mit der gleichen Länge entfernt werden konnte #(was eigentlich keinen Sinn ergab).

Python 2, 71 Bytes

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

Beispiellauf:

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

Mit zwei gegebenen Zeichenfolgen können x,ywir das erste Zeichen von nehmen xund es jedem Ergebnis des rekursiven Aufrufs voranstellen, wobei es fehlt f(x[1:],y). Oder wir können dasselbe mit xund ygeschaltet machen. Indem wir x,yentweder den Eingang poder dessen Umkehrung `p [:: - 1] nehmen, erhalten wir beide Möglichkeiten.

Um zu vermeiden, dass ein leerer String entnommen wird x, schließen wir logischerweise mit x and. Wenn beide Strings leer sind, kann keiner der Strings leer sein xund wir erhalten eine leere Liste von Möglichkeiten, die wir mit ordem richtigen Basisfall beheben [''].

Eine ähnliche generative Strategie in Python 3 (73 Byte):

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

Hier ist, wie gewünscht, eine Python-Antwort:

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

Dank Sp3000 für das Essen von 4 Bytes :)

CJam, 38

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

Probieren Sie es online aus

Dynamische Programmierung (mit gespeicherter Rekursion).

Erläuterung:

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 Bytes

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

Teste es hier.

Das fühlt sich wirklich golfen an, aber bisher habe ich nur 4 alternative Lösungen gefunden, die alle die gleiche Byteanzahl haben:

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)

Die Grundidee besteht darin, alle Permutationen von 0s und 1s zu generieren , die der Zeichenfolge entsprechen, aus der die einzelnen Zeichen im Ergebnis entnommen werden sollen. Das ist alles bis einschließlich der e!. Der Rest zieht dann einfach die Zeichen in dieser Reihenfolge aus den beiden Zeichenfolgen heraus.

JavaScript (Firefox 30-57), 88 84 81 Bytes

(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)]

Bearbeiten: 4 Bytes durch Verbesserung meiner Abbruchbedingung gespeichert. 3 Bytes gespart dank @ edc65.

Brachylog , 8 Bytes

p~cᵐz₁cc

Probieren Sie es online!

Nimmt die Eingabe als Liste von zwei Zeichenfolgen durch die Eingabevariable und generiert alle möglichen Verschachtelungen durch die Ausgabevariable. Da die Testfälle doppelte Verschachtelungen zuzulassen scheinen, wenn es gemeinsame Buchstaben gibt, habe ich nicht darauf geachtet, sie zu vermeiden, aber dies erzeugt viel mehr Duplikate und das nicht nur mit gemeinsamen Buchstaben. (Wenn dies nicht zulässig ist, die Duplikate für gemeinsam genutzte Buchstaben jedoch nicht erforderlich sind, fügen Sie einfach drei Bytes hinzu, um sie {}ᵘals Liste ohne Duplikate auszugeben.)

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.

Im Wesentlichen generiert dies jede Partition beider Zeichenfolgen und verschachtelt sie dann in der normalen deterministischen Weise in einer beliebigen Reihenfolge. Die zusätzlichen doppelten Verschachtelungen sind auf Partitionspaare zurückzuführen, bei denen der Unterschied zwischen der Länge der ersten und der Länge der zweiten einen anderen Wert als 0 oder 1 hat, sodass einer von ihnen Abschnitte aufweist, die am Ende miteinander verkettet werden. So erzeugen Sie eine Ausgabe mit den gleichen Multiplizitäten wie die Beispielausgabe:

Brachylog , 17 Bytes

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

Probieren Sie es online!

Der zusätzliche Code {lᵐ-ℕ<2&}schlägt bei jedem Partitionspaar fehl, bei dem keine zusätzlichen Divisionen vorgenommen werden. (Ich habe die Kopfzeile in TIO geändert, um sie mit Anführungszeichen zu drucken, damit die Ausgabe in der Python-Shell einfacher überprüft werden kann.)

MATL , 34 30 Bytes

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

Dies basiert auf einer Idee aus dieser Antwort : Wenn die Länge der Zeichenfolgen mund ist n, zähle alle m+nBitmuster mit mgesetzten Bits auf. Eine Möglichkeit, diese Aufzählung durchzuführen, besteht darin, alle Permutationen eines Vektors mit mEinsen und nNullen zu generieren und dann Duplikate zu entfernen.

Probieren Sie es online!

Erläuterung

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

Ruby, 83 Bytes

Eine rekursive Funktion, die zurückgibt, [a+b]wenn eine dieser Zeichenfolgen leer ist. Andernfalls wird eine Liste von Zeichenfolgen zurückgegeben, a[0] + every string in v[a[1..-1],b]die zu einer Liste von Zeichenfolgen hinzugefügt wurdenb[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]}

Batch, 154 152 Bytes

@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%