CODEWITHSUNDEEP
pythonalgorithm
user810606
user810606

Reputation:

How to calculate all interleavings of two lists?

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.

Upvotes: 5

Views: 1550

Answers (4)

Abhijit
Abhijit

Reputation: 63787

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)Clen(B)

= 4C2

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

Upvotes: 6

Knoothe
Knoothe

Reputation: 1218

Hint: Suppose each list had the same elements (but different between the list), i.e. one list was completely Red (say r of them), and the other was Blue (say b of them).

Each element of the output contains r+b or them, r of which are red.

Seems like others have spoilt it for you, even though you didn't ask for a solution (but they have a very good explanation)

So here it the code I wrote up quickly.

import itertools

def interleave(lst1, lst2):
    r,b = len(lst1), len(lst2)
    for s in itertools.combinations(xrange(0,r+b), r):
        lst = [0]*(r+b)
        tuple_idx,idx1,idx2 = 0,0,0
        for i in xrange(0, r+b):
            if tuple_idx < r and i == s[tuple_idx]:
                lst[i] = lst1[idx1]
                idx1 += 1
                tuple_idx += 1
            else: 
                lst[i] = lst2[idx2]
                idx2 += 1
        yield lst


def main():
    for s in interleave([1,2,3], ['a','b']):
        print s

if __name__ == "__main__":
    main()

The basic idea is to map the output to (r+b) choose r combinations.

Upvotes: 2

Slater Victoroff
Slater Victoroff

Reputation: 21934

You can try something a little closer to the metal and more elegant(in my opinion) iterating through different possible slices. Basically step through and iterate through all three arguments to the standard slice operation, removing anything added to the final list. Can post code snippet if you're interested.

Upvotes: 0

salezica
salezica

Reputation: 77119

As suggested by @airza, the itertools module is your friend.

If you want to avoid using encapsulated magical goodness, my hint is to use recursion.

Start playing the process of generating the lists in your mind, and when you notice you're doing the same thing again, try to find the pattern. For example:

  1. Take the first element from the first list
  2. Either take the 2nd, or the first from the other list
  3. Either take the 3rd, or the 2nd if you didn't, or another one from the other list
  4. ...

Okay, that is starting to look like there's some greater logic we're not using. I'm just incrementing the numbers. Surely I can find a base case that works while changing the "first element, instead of naming higher elements?

Play with it. :)

Upvotes: 1

Related Questions