List of all permutations of a binary sequence

Question

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.

Wouldn't two nodes only have `[left]` and `[right]` as possible paths between the start and end node? If this is coming from a hw or online question could you include the original text? — 0x263A, Dec 07 '21 at 22:22
@j1-lee, I gave the list example only for two nodes, so less than in the picture, to save myself writing the permutations. — kuntakinte, Dec 07 '21 at 22:33
@0x263A , I don't quite understand your remark? I didn't take it from anywhere, it's a problem that I came across when doing my own project. — kuntakinte, Dec 07 '21 at 22:36
@j1-lee, yes correct. Seems that itertools.product does the job indeed! — kuntakinte, Dec 07 '21 at 22:38
Does this answer your question? [How to generate all permutations of a list?](https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list) specifically, [this answer](https://stackoverflow.com/a/170248/6045800) — Tomerikoo, Dec 07 '21 at 22:41

score 0 · Accepted Answer · answered Dec 07 '21 at 22:18

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

Thank you, this is what I needed! – kuntakinte Dec 07 '21 at 22:37 — kuntakinte, Dec 07 '21 at 22:37

List of all permutations of a binary sequence

1 Answers1