Recientemente vi esta pregunta en stackoverflow. Es una gran pregunta, pero hay un problema fatal con la pregunta. Piden la mejor manera de hacerlo. Por ejemplo, el más fácil de leer, el más idiomático, el más ordenado, etc. ¿No saben que eso no es lo que importa? ¡Se supone que debes preguntar cómo hacerlo con la menor cantidad de bytes de código!

Como dudo que esa pregunta sea apreciada en stackoverflow, decidí preguntarla aquí.

El reto

Debe escribir el programa o función más breve posible que genere todas las formas posibles de intercalar dos cadenas arbitrarias. Por ejemplo, si las dos cadenas son 'ab'y 'cd', la salida es:

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

Como puede ver, asiempre está antes by csiempre está antes d.

IO puede estar en cualquier formato razonable. Use este código de Python para verificar y verificar su salida. (crédito: 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

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

Como de costumbre, se aplican las lagunas estándar y gana la respuesta más corta en bytes. Dado que la pregunta era originalmente sobre Python, me encantaría ver la respuesta más corta de Python. (Y no, pyth no es python). Sin embargo, se alientan las respuestas en cualquier idioma.

Pyth, 26

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

Pruébalo aquí

Esta es una implementación muy básica de la fórmula recursiva dada. Define una función gque realiza la tarea requerida. El enlace es un programa modificado que lee las cadenas de la nueva línea STDIN separadas, para ser más conveniente. Para llamar a la función do g<string1><string2>.

Expansión:

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

Las dos llamadas recursivas son muy similares, pero ya no he podido encontrar una manera de jugar golf.

Haskell, 53 48 bytes

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

Define una función %para la cual a%bcon cadenasa,b da una lista de cadenas.

Dadas dos cadenas, elegimos una de las dos para tomar el primer personaje. Luego recurrimos en el resto de dos cadenas, anteponiendo ese carácter a cada resultado.

Cuando una de las cadenas está vacía, el único resultado posible es la otra cadena. ""%""=[""]También sería suficiente, pero es más largo.

53 bytes:

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

Define una función %para la cual a%dcon cadenasa,d da una lista de cadenas.

La función se define de forma recursiva. Si tomamos un carácter de la primera cadena, debe anteponerse a cada resultado de la llamada recursiva en el resto de la primera cadena con la segunda cadena. Simétricamente para la otra cuerda.

Para el caso base, si una de las cadenas está vacía, el resultado es una lista de un solo elemento de su concatenación. Esto es más corto que dos casos para cada cadena que está vacía.

Haskell, 47

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

% es el operador que resuelve este desafío.

#es un operador que toma dos listas y encuentra todas las formas de intercalarlas de modo que el primer carácter sea de la primera cadena (con un caso de borde, si la primera lista está vacía, entonces el resultado es una lista vacía) recurriendo a %.

entonces, %funciona simplemente aplicando #dos veces.

Editar: La versión anterior tenía un error en el que ""%""regresó ["",""], así que lo arreglé. Se solucionó agregando un caso base a %, que luego permitió eliminar un caso base de la misma longitud #(que realmente no tenía mucho sentido).

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

Ejemplo de ejecución:

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

Dadas dos cadenas x,y, podemos tomar el primer carácter xy anteponerlo a cada resultado de la llamada recursiva sin él f(x[1:],y). O podemos hacer lo mismo con xyy cambiar. Al tomar x,ycomo entrada po como inversión `p [:: - 1], obtenemos ambas posibilidades.

Para evitar tomar de una cadena vacía x, hacemos un cortocircuito lógico con x and. Si ambas cadenas están vacías, ninguna cadena puede serx y obtenemos una lista vacía de posibilidades, que corregimos con orel caso base correcto[''] .

Una estrategia generativa similar en Python 3 (73 bytes):

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

Según lo solicitado, aquí hay una respuesta de 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])]

Gracias Sp3000 por comer 4 bytes :)

CJam, 38

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

Pruébalo en línea

Programación dinámica (usando recursión memorable).

Explicación:

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}

Pruébalo aquí.

Esto se siente realmente golfable, pero hasta ahora solo he encontrado 4 soluciones alternativas que tienen el mismo número de bytes:

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)

La idea básica es generar todas las permutaciones de 0s y 1S que corresponde a qué cadena de tomar cada carácter en el resultado de. Eso es todo, incluido el e!. El resto simplemente saca caracteres en ese orden de las dos cadenas.

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

Editar: guardado 4 bytes al mejorar mi condición de terminación. Guardado 3 bytes gracias a @ edc65.

Brachylog , 8 bytes

p~cᵐz₁cc

Pruébalo en línea!

Toma la entrada como una lista de dos cadenas a través de la variable de entrada y genera todos los entrelazamientos posibles a través de la variable de salida. Dado que los casos de prueba parecen permitir entrelazados duplicados donde hay letras compartidas, no he tenido cuidado de evitarlos, pero esto genera muchos más duplicados y no solo con letras compartidas. (Si esto no está permitido, pero los duplicados de letras compartidas no son necesarios, solo agregue tres bytes para envolverlos {}ᵘpara la salida como una lista sin duplicados).

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.

Esencialmente, esto genera cada partición de ambas cadenas, luego las intercala en la forma determinista normal en cualquier orden. Los entrelazados duplicados adicionales se deben a pares de particiones donde la diferencia entre la longitud de la primera y la longitud de la segunda tiene algún valor distinto de 0 o 1, de modo que uno de ellos tiene fragmentos que se concatenan entre sí al final. Entonces, para producir una salida con las mismas multiplicidades que la salida de muestra:

Brachylog , 17 bytes

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

Pruébalo en línea!

El código extra {lᵐ-ℕ<2&}falla cualquier par de particiones donde se realizan divisiones extrañas. (Modifiqué el encabezado en TIO para imprimir con comillas para facilitar la comprobación de salida en el shell de Python).

MATL , 34 30 bytes

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

Esto utiliza una idea de esta respuesta : si las longitudes de las cadenas son my n, enumere todos m+nlos patrones de mbits con los bits establecidos. Una forma de hacer esa enumeración es: generar todas las permutaciones de un vector con munos y nceros y luego eliminar duplicados.

Pruébalo en línea!

Explicación

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

Una función recursiva que devuelve [a+b]si cualquiera de esas cadenas está vacía. De lo contrario, devuelve una lista de cadenas a[0] + every string in v[a[1..-1],b]agregadas a una lista de cadenasb[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]}

Lote, 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%