Sequential permutations in Python
I recently needed the functionality in Python to take a series of lists and find all possible combinations of one item from each list. For example, take the following lists that, together, make up my dinner:
wine = ["white", "red", "mad dog 20/20"] first_course = ["salad", "soup"] second_course = ["steak", "chicken"] desert = ["pie", "cake"]
We want to have a glass of wine, a first course, a second course, and a desert with each meal, but we don’t want the same meal twice. Let’s complicate things by saying we also might want to skip desert on some meals. With the code (below), we only need to modify the desert list:
desert = ["pie", "cake", None]
Here is the function I came up with:
def sequence_permutations(*args): """ Generate a list of permutations using one element each from each list in *args, maintaining the order in which the args were named. """ perms = [] for x in args[0]: for y in args[1]: if isinstance(x, list): z = x[:] z.append(y) perms.append(z) else: perms.append([x, y]) if len(args) > 2: perms = sequence_permutations(perms, *args[2:]) return perms
This function works recursively. You pass it a series of lists and it continues to run until it has exhausted all options in all lists, finally returning a list of lists.
It’s worth pointing out the line:
z = x[:]
This creates a copy of x in z. If we did not do this, the next line would read:
z.append(y)
…which would create an infinite loop: since we are iterating over y for each element in x, if we add y to the end of x before we terminate the iterations, we end up exponentially increasing the length of x by the length of y on each iteration. The copy statement avoids this.
So, now we run:
print "Running sequence_permutations on your dinner:" wine = ["white", "red", "mad dog 20/20"] first_course = ["salad", "soup"] second_course = ["steak", "chicken"] desert = ["pie", "cake", None] for pattern in sequence_permutations(wine, first_course, second_course, desert): print pattern
And here is what we get:
Running sequence_permutations on your dinner: ['white', 'salad', 'steak', 'pie'] ['white', 'salad', 'steak', 'cake'] ['white', 'salad', 'steak', None] ['white', 'salad', 'chicken', 'pie'] ['white', 'salad', 'chicken', 'cake'] ['white', 'salad', 'chicken', None] ['white', 'soup', 'steak', 'pie'] ['white', 'soup', 'steak', 'cake'] ['white', 'soup', 'steak', None] ['white', 'soup', 'chicken', 'pie'] ['white', 'soup', 'chicken', 'cake'] ['white', 'soup', 'chicken', None] ['red', 'salad', 'steak', 'pie'] ['red', 'salad', 'steak', 'cake'] ['red', 'salad', 'steak', None] ['red', 'salad', 'chicken', 'pie'] ['red', 'salad', 'chicken', 'cake'] ['red', 'salad', 'chicken', None] ['red', 'soup', 'steak', 'pie'] ['red', 'soup', 'steak', 'cake'] ['red', 'soup', 'steak', None] ['red', 'soup', 'chicken', 'pie'] ['red', 'soup', 'chicken', 'cake'] ['red', 'soup', 'chicken', None] ['mad dog 20/20', 'salad', 'steak', 'pie'] ['mad dog 20/20', 'salad', 'steak', 'cake'] ['mad dog 20/20', 'salad', 'steak', None] ['mad dog 20/20', 'salad', 'chicken', 'pie'] ['mad dog 20/20', 'salad', 'chicken', 'cake'] ['mad dog 20/20', 'salad', 'chicken', None] ['mad dog 20/20', 'soup', 'steak', 'pie'] ['mad dog 20/20', 'soup', 'steak', 'cake'] ['mad dog 20/20', 'soup', 'steak', None] ['mad dog 20/20', 'soup', 'chicken', 'pie'] ['mad dog 20/20', 'soup', 'chicken', 'cake'] ['mad dog 20/20', 'soup', 'chicken', None]
This is outstanding. I need to do something similar, and I was really struggling to come up with a solution. Thanks!