Vi recentemente essa pergunta no stackoverflow. É uma ótima pergunta, mas há um problema fatal com a pergunta. Eles estão pedindo a melhor maneira de fazê-lo. Por exemplo, mais fácil de ler, mais idiomático, mais organizado etc. Eles não sabem que não é isso que importa? Você deveria perguntar como fazê-lo com o menor número de bytes de código!

Como duvido que essa pergunta seja apreciada no stackoverflow, decidi perguntar aqui.

O desafio

Você deve escrever o programa ou função mais curto possível que gere todas as formas possíveis de intercalar duas seqüências de caracteres arbitrárias. Por exemplo, se as duas cadeias são 'ab'e 'cd', a saída é:

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

Como você pode ver, aé sempre antes b, e cé sempre antes d.

O IO pode estar em qualquer formato razoável. Use este código python para verificar e verificar sua saída. (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

IO de amostra:

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 costume, as brechas padrão se aplicam e a resposta mais curta em bytes vence. Como a pergunta era originalmente sobre python, eu adoraria ver a resposta mais curta em python. (E não, pyth não é python). No entanto, respostas em qualquer idioma são incentivadas.

Pyth, 26

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

Experimente aqui

Esta é uma implementação muito básica da fórmula recursiva fornecida. Ele define uma função gque executa a tarefa necessária. O link é um programa modificado que lê as seqüências de caracteres de nova linha STDIN separadas, para ser mais conveniente. Para chamar a função do g<string1><string2>.

Expansão:

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

As duas chamadas recursivas são muito parecidas, mas não consegui mais encontrar uma maneira de jogar golfe.

Haskell, 53 48 bytes

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

Define uma função %para a qual, a%bcom strings, a,bfornece uma lista de strings.

Dadas duas seqüências, escolhemos uma das duas para pegar o primeiro caractere. Em seguida, repetimos o restante de duas cadeias, acrescentando esse caractere a cada resultado.

Quando uma das seqüências está vazia, o único resultado possível é a outra. ""%""=[""]também seria suficiente, mas é mais longo.

53 bytes:

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

Define uma função %para a qual, a%dcom strings, a,dfornece uma lista de strings.

A função é definida recursivamente. Se pegarmos um caractere da primeira string, ele deverá ser anexado a cada resultado da chamada recursiva no restante da primeira string com a segunda string. Simetricamente para a outra corda.

Para o caso base, se uma das seqüências estiver vazia, o resultado será uma lista de elementos únicos de sua concatenação. Isso é mais curto que dois casos para cada string estar vazia.

Haskell, 47

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

% é o operador que resolve esse desafio.

#é um operador que pega duas listas e encontra todas as maneiras de intercalá-las, de modo que o primeiro caractere seja da primeira string (com uma caixa de aresta - se a primeira lista estiver vazia, o resultado será uma lista vazia), recorrendo a %.

então, %funciona aplicando apenas #duas vezes.

Edit: A versão anterior teve um bug no qual ""%""retornou ["",""], então eu o consertei. Foi corrigido adicionando uma caixa base a %, que permitiu remover uma caixa base do mesmo comprimento #(o que realmente não fazia muito 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['']

Exemplo de execução:

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

Dadas duas seqüências x,y, podemos pegar o primeiro caractere de xe anexá-lo a cada resultado da chamada recursiva com ele ausente f(x[1:],y). Ou, podemos fazer o mesmo com xe yalternado. Tomando x,ycomo entrada pou como sua inversão `p [:: - 1], obtemos as duas possibilidades.

Para evitar retirar de uma string vazia x, fazemos um curto-circuito lógico com x and. Se ambas as strings estiverem vazias, nenhuma das strings pode ser xe nós obtemos uma lista vazia de possibilidades, com oras quais corrigimos o caso base correto [''].

Uma estratégia generativa semelhante no 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

Conforme solicitado, aqui está uma resposta em 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])]

Obrigado Sp3000 por comer 4 bytes :)

CJam, 38

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

Experimente online

Programação dinâmica (usando recursão memorizada).

Explicação:

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 aqui.

Parece realmente fácil de jogar, mas até agora encontrei apenas 4 soluções alternativas com a mesma contagem 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)

A idéia básica é a de gerar todas as permutações de 0s e 1s correspondente a que a corda para levar cada personagem no resultado de. Isso é tudo, inclusive o e!. O resto simplesmente seleciona os caracteres nessa ordem das duas seqüências de caracteres.

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

Edit: Salvo 4 bytes, melhorando minha condição de terminação. Economizou 3 bytes graças a @ edc65.

Braquilog , 8 bytes

p~cᵐz₁cc

Experimente online!

Toma a entrada como uma lista de duas cadeias através da variável de entrada e gera todas as intercalações possíveis através da variável de saída. Como os casos de teste parecem permitir intercalações duplicadas onde existem cartas compartilhadas, não tomei o cuidado de evitá-las, mas isso gera muito mais duplicatas e não apenas com cartas compartilhadas. (Se isso não for permitido, mas as duplicatas de letras compartilhadas não forem necessárias, basta adicionar três bytes para quebrar {}ᵘa saída como uma lista sem duplicatas.)

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.

Essencialmente, isso gera todas as partições de ambas as seqüências e as intercala da maneira determinística normal em qualquer ordem. As intercalações duplicadas extras são devidas a pares de partições em que a diferença entre o comprimento do primeiro e o comprimento do segundo tem algum valor diferente de 0 ou 1, para que um deles tenha pedaços que sejam concatenados entre si no final. Portanto, para produzir saída com as mesmas multiplicidades da saída de amostra:

Braquilog , 17 bytes

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

Experimente online!

O código extra {lᵐ-ℕ<2&}falha em qualquer par de partições em que são feitas divisões estranhas. (Alterei o cabeçalho no TIO para imprimir com aspas para facilitar a verificação de saída no shell do Python.)

MATL , 34 30 bytes

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

Isso usa uma idéia desta resposta : se os comprimentos das strings forem me n, enumere todos os m+npadrões de mbits com os bits definidos. Uma maneira de fazer essa enumeração é: gerar todas as permutações de um vetor com muns e nzeros e depois remover duplicatas.

Experimente online!

Explicação

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

Uma função recursiva que retorna [a+b]se uma dessas cadeias estiver vazia. Caso contrário, ele retornará uma lista de strings a[0] + every string in v[a[1..-1],b]adicionadas a uma lista de stringsb[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%