All possible ways to interleave two strings

Question

I recently saw this question on stackoverflow. It's a great question, but there's one fatal problem with the question. They are asking for the best way to do it. E.g, easiest to read, most idiomatic, neatest etc. Don't they know that isn't what matters? You're supposed to ask about how to do it with the fewest bytes of code!

Since I doubt that question will be appreciated on stackoverflow, I decided to ask it here.

The challenge

You must write the shortest possible program or function that generates all possible ways to interleave any two arbitrary strings. For example, if the two strings are 'ab' and 'cd', the output is:

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

As you can see, a is always before b, and c is always before d.

IO can be in any reasonable format. Use this python code to verify to check your output. (credit: 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

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

As usual, standard loopholes apply, and the shortest answer in bytes wins. Since the question was originally about python, I'd love to see the shortest python answer. (And no, pyth is not python). However, answers in any language are encouraged.

Answer 1

Pyth, 26

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

Try it here

This is a very basic implementation of the given recursive formula. It defines a function g that performs the required task. The link is a modified program that reads the strings from STDIN newline separated, to be more convenient. To call the function do g<string1><string2>.

Expansion:

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

The two recursive calls are very similar, but I haven't been able to find a way to golf them any more.

Answer 2

Haskell, 53 48 bytes

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

Defines a function % for which a%b with strings a,b gives a list of strings.

Given two strings, we choose one of the two to take the first character from. We then recurse on the remainder of two strings, prepending that character to each result.

When one of the string is empty, the only possible result is the other string. ""%""=[""] would also suffice, but's it's longer.

---

53 bytes:

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

Defines a function % for which a%d with strings a,d gives a list of strings.

The function is defined recursively. If we take a character from the first string, then it must be prepended to each result of the recursive call on the remained of the first string with the second string. Symmetrically for the other string.

For the base case, if one of the strings is empty, the result is a single-element list of their concatenation. This is shorter than two cases for each string being empty.

Answer 3

Haskell, 47

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

% is the operator that solves this challenge.

# is an operator that takes in two lists and finds all the ways to interleave them such that the first character is from the first string (with an edge case - if the first list is empty, then the result is an empty list) by recursing to %.

then, % works by just applying # twice.

Edit: The previous version had a bug in which ""%"" returned ["",""], so I fixed it up. It was fixed by adding a base case to %, which then allowed to remove a base case of the same length from # (which really, didn't make much sense).

Answer 4

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

Example run:

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

Given two strings x,y we can take the first character of x and prepend it to each result of the recursive call with it missing f(x[1:],y). Or, we can do the same with x and y switched. By taking x,y as either the input p or its reversal `p[::-1], we get both possibilities.

To avoid taking from an empty string x, we logical short-circuit with x and. If both strings are empty, neither string can be x and we get and empty list of possibilities, which we fix with or to the correct base case [''].

A similar generative strategy in 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)

Answer 5

Python, 80

As requested, here's a python answer:

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

Thanks Sp3000 for eating 4 bytes :)

Answer 6

Brachylog, 8 bytes

p~cᵐz₁cc

Try it online!

Takes input as a list of two strings through the input variable, and generates all possible interleavings through the output variable. Since the test cases seem to permit duplicate interleavings where there are shared letters, I haven't taken any care to avoid them, but this generates a lot more duplicates and not just with shared letters. (If this isn't allowed, but the shared letter duplicates aren't necessary, just add three bytes to wrap in {}ᵘ for output as a list with no duplicates.)

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.

Essentially, this generates every partition of both strings, then interleaves them in the normal deterministic fashion in either order. The extra duplicate interleavings are due to partition pairs where the difference between the length of the first and the length of the second has some value other than 0 or 1, so that one of them has chunks that get concatenated to each other at the end. So, to produce output with the same multiplicities as the sample output:

Brachylog, 17 bytes

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

Try it online!

The extra code, {lᵐ-ℕ<2&}, fails any partition pair where any extraneous divisions are made. (I altered the header on TIO to print with quotes for easier output checking in the Python shell.)

Answer 7

CJam, 38

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

Try it online

Dynamic programming (using memoized recursion).

Explanation:

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

Answer 8

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: Saved 4 bytes by improving my termination condition. Saved 3 bytes thanks to @edc65.

Answer 9

CJam, 32 bytes

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

Test it here.

This feels really golfable, but so far I've only found 4 alternative solutions that all have the same byte count:

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)

The basic idea is to generate all permutations of 0s and 1s corresponding to which string to take each character in the result from. That's everything up to and including the e!. The rest simply pulls out characters in that order from the two strings then.

Answer 10

MATL, 34 30 bytes

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

This uses an idea from this answer: if the lenghts of the strings are m and n, enumerate all m+n bit patterns with m bits set. One way do that that enumeration is: generate all permutations of a vector with m ones and n zeros and then remove duplicates.

Try it online!

Explanation

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

Answer 11

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%

Answer 12

Ruby, 83 bytes

A recursive function that returns [a+b] if either of those strings are empty. Otherwise, it returns a list of strings a[0] + every string in v[a[1..-1],b] added to a list of string b[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]}