How to calculate all interleavings of two lists?

algorithm, python

Solution

Itertools would not be capable enough to handle this problem and would require some bit of understanding of the pegs and holes problem

Consider your example list

A = [1, 2 ] B = [3, 4 ]

There are four holes (`len(A) + len(B)`) where you can place the elements (pegs)

|   ||   ||   ||   |
|___||___||___||___|

In Python you can represent empty slots as a list of `None`

slots = [None]*(len(A) + len(B))

The number of ways you can place the elements (pegs) from the second list into the pegs is simply, the number of ways you can select slots from the holes which is

`len(A) + len(B)`C`len(B)`

= `4`C`2`

= `itertools.combinations(range(0, len(len(A) + len(B)))`

which can be depicted as

|   ||   ||   ||   |  Slots
|___||___||___||___|  Selected

  3    4              (0,1)
  3         4         (0,2)
  3              4    (0,3) 
       3    4         (1,2) 
       3         4    (1,3)
            3    4    (2,3)

Now for each of these slot position fill it with elements (pegs) from the second list

for splice in combinations(range(0,len(slots)),len(B)):
    it_B = iter(B)
    for s in splice:
        slots[s] = next(it_B)

Once you are done, you just have to fill the remaining empty slots with the elements (pegs) from the first list

    it_A = iter(A)
    slots = [e if e else next(it_A) for e in slots]

Before you start the next iteration with another slot position, flush your holes

    slots = [None]*(len(slots))

A Python implementation for the above approach

def slot_combinations(A,B):
    slots = [None]*(len(A) + len(B))
    for splice in combinations(range(0,len(slots)),len(B)):
        it_B = iter(B)
        for s in splice:
            slots[s] = next(it_B)
        it_A = iter(A)
        slots = [e if e else next(it_A) for e in slots]
        yield slots
        slots = [None]*(len(slots))

And the O/P from the above implementation

list(slot_combinations(A,B))
[[3, 4, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [1, 3, 4, 2], [1, 3, 2, 4], [1, 2, 3, 4]]

Problem

I want to create a function that takes in two lists, the lists are not guaranteed to be of equal length, and returns all the interleavings between the two lists. Input: Two lists that do not have to be equal in size. Output: All possible interleavings between the two lists that preserve the original list's order. Example: AllInter([1,2],[3,4]) -> [[1,2,3,4], [1,3,2,4], [1,3,4,2], [3,1,2,4], [3,1,4,2], [3,4,1,2]] I do not want a solution. I want a hint.

Original source