CODEWITHSUNDEEP
pythonlistpermutation
ben
ben

Reputation: 277

Permutations of the elements of two lists with order restrictions

I would like to merge two input lists together and get all permutations of their elements such that the ordering of the elements in each input list is retained.

For example, if I have two lists: ['b','a'] and ['c','d'], I would like to get the following lists: 

['b', 'a', 'c', 'd'], 
['b', 'c', 'a', 'd'], 
['b', 'c', 'd', 'a'], 
['c', 'b', 'a', 'd'], 
['c', 'b', 'd', 'a'], 
['c', 'd', 'b', 'a']

where the order of the elements from the original lists is retained (b comes before a, c comes before d).

I have found a post dealing with a similar problem but using strings as inputs instead of lists: Restricted Permutations of Strings in Python. For example, with the strings "ba" and "cd" as inputs, strings "bacd", "bcad", "bcda", "cbad", "cbda", "cdba" will be returned.

I have tried to adapt the code there to my problem, but it didn't work. Using the same example as above, I got [None, None, None, None, None, None] instead of the 6 lists that I expected. Below is the code I used. 

def ordered_permutations(list1, list2):
    perms = []
    if len(list1) + len(list2) == 1:
        return [list1 or list2]
    if list1:
        for item in ordered_permutations(list1[1:], list2):
            perms.append([list1[0]].append(item))
    if list2:
        for item in ordered_permutations(list1, list2[1:]):
            perms.append([list2[0]].append(item))
    return perms

Upvotes: 1

Views: 880

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121834

list.append() returns None as the list is altered in-place. You should use concatenation instead:

def ordered_permutations(list1, list2):
    perms = []
    if len(list1) + len(list2) == 1:
        return [list1 or list2]
    if list1:
        for item in ordered_permutations(list1[1:], list2):
            perms.append([list1[0]] + item)
    if list2:
        for item in ordered_permutations(list1, list2[1:]):
            perms.append([list2[0]] + item)
    return perms

This then produces your required output:

>>> def ordered_permutations(list1, list2):
...     perms = []
...     if len(list1) + len(list2) == 1:
...         return [list1 or list2]
...     if list1:
...         for item in ordered_permutations(list1[1:], list2):
...             perms.append([list1[0]] + item)
...     if list2:
...         for item in ordered_permutations(list1, list2[1:]):
...             perms.append([list2[0]] + item)
...     return perms
... 
>>> for combo in ordered_permutations(['b','a'], ['c', 'd']):
...     print combo
... 
['b', 'a', 'c', 'd']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'b', 'a']

Upvotes: 2

Related Questions