How to weave two lists using recursion in Python

user_3889065 0
Viewed 176

I want to weave two lists and output all the possible results.
For example,
input: two lists l1 = [1, 2], l2 = [3, 4]
output: [1, 2, 3, 4], [1, 3, 2, 4], [1, 3, 4, 2], [3, 1, 2, 4], [3, 1, 4, 2], [3, 4, 1, 2]
Note: I need to keep the order in each list (e.g. 1 is always before 2, and 3 is always before 4)

The way I am solving this is by removing the head from one list, recursing, and then doing the same thing with the other list. The code is below:

all_possibles = []
def weaveLists(first, second, added):
    if len(first) == 0 or len(second) == 0:
        res = added[:]
        res += first[:]
        res += second[:]
        all_possibles.append(res)
        return

    cur1 = first[0]
    added.append(cur1)
    first = first[1:]
    weaveLists(first, second, added)
    added = added[:-1]
    first = [cur1] + first

    cur2 = second[0]
    added.append(cur2)
    second = second[1:]
    weaveLists(first, second, added)
    added = added[:-1]
    second = [cur2] + second


weaveLists([1, 2], [3, 4], [])
print(all_possibles)

The result I got is: [[1, 2, 3, 4], [1, 3, 2, 4], [1, 3, 4, 2], [1, 3, 1, 2, 4], [1, 3, 1, 4, 2], [1, 3, 1, 4, 1, 2]]

I couldn't figure out why for the last three lists, the heading 1 from the first list is not removed.

Can anyone help? Thanks!

recursion list python
2 Answers

Here is another way to do it: we generate the possible indices of the items of the first list inside the weaved list, and fill the list accordingly.

We can generate the indices with itertools.combinations: it's the combinations of the indices of the weaved list, taking len(first_list) of them each time.

from itertools import combinations
​
def weave(l1, l2):
    total_length = len(l1) + len(l2)
    # indices at which to put items from l1 in the weaved output
    for indices in combinations(range(total_length), r=len(l1)):
        out = []
        it1 = iter(l1)
        it2 = iter(l2)
        for i in range(total_length):
            if i in indices:
                out.append(next(it1))
            else:
                out.append(next(it2))
        yield out

Sample run:

l1 = [1, 2]
l2 = [3, 4]
​
for w in weave(l1, l2):
    print(w)
    
​
[1, 2, 3, 4]
[1, 3, 2, 4]
[1, 3, 4, 2]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]

Another sample run with a longer list:

l1 = [1, 2]
l2 = [3, 4, 5]
​
for w in weave(l1, l2):
    print(w)
    
​
[1, 2, 3, 4, 5]
[1, 3, 2, 4, 5]
[1, 3, 4, 2, 5]
[1, 3, 4, 5, 2]
[3, 1, 2, 4, 5]
[3, 1, 4, 2, 5]
[3, 1, 4, 5, 2]
[3, 4, 1, 2, 5]
[3, 4, 1, 5, 2]
[3, 4, 5, 1, 2]
user_5500940

The reason you get those unexpected results is that you mutate added at this place:

added.append(cur1)

...this will affect the caller's added list (unintentionally). While the "undo" operation is not mutating the list:

added = added[:-1]

This creates a new list, and therefore this "undo" action does not roll back the change in the list of the caller.

The easy fix is to replace the call to append with:

added = added + [cur1]

And the same should happen in the second block.

It is easier if you pass the new values for the recursive call on-the-fly, and replace those two code blocks with just:

weaveLists(first[1:], second, added + [first[0]])
weaveLists(first, second[1:], added + [second[0]])
user_54598390
Related