List of all permutations of a binary sequence

December 8, 2021

I need to visit n consecutive nodes. From every node I can take either path to the Left or path to the Right, leading me to the next node. I would like to get a list of lists of all possible permutations of paths that can lead me from the first node to the last one. So, in case i have two nodes I would like to get:

[[Left,Left],[Left,Right],[Right,Right],[Right,Left]]

I guess I need to use some basic recursive function but I can’t quite wrap my head around it.

>Solution :

Recursion is not needed here. You can use itertools.product with a number of copies of ['Left', 'Right'], for example:

from itertools import product

options = ['Left', 'Right']
N = 3

print(list(product(*(options,)*N)))

gives:

[('Left', 'Left', 'Left'), ('Left', 'Left', 'Right'), ('Left', 'Right', 'Left'), ('Left', 'Right', 'Right'), ('Right', 'Left', 'Left'), ('Right', 'Left', 'Right'), ('Right', 'Right', 'Left'), ('Right', 'Right', 'Right')]

If you wish, you can convert the inner elements to lists instead of tuples:

print([list(t) for t in (product(*(options,)*N))])

gives:

[['Left', 'Left', 'Left'], ['Left', 'Left', 'Right'], ['Left', 'Right', 'Left'], ['Left', 'Right', 'Right'], ['Right', 'Left', 'Left'], ['Right', 'Left', 'Right'], ['Right', 'Right', 'Left'], ['Right', 'Right', 'Right']]