Search code examples
pythonpermutation

List of all permutations of a binary sequence

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.

enter image description here

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