Generate all length-n permutations of True/False?

Question

This problem came up while trying to write code for a truth-table generating function.

How can I generate a list of lists of all length-n permutations of True and False? In other words, given a list of elements [True, False], how can I generate all permutations of all possible length-n combinations of those elements?

For example:

n=2 length-2 permutations are:

[[True, True], [True, False], [False, True], [False, False]]

n=3 the length-3 permutations are:

[[False, False, False],[False,False,True],
[False,True,False],[False,True,True],
[True,False,False],[True,False,True],[True,True,False],[True,True,True]]

I know there's 2^n lists in this list. I also have considered using itertools.product, but that only seems to give permutations of a specific combination. In this case, I think I want to generate permutations of ALL combinations of a length-n list of true/false.

Answer 1

Use itertools.product:

>>> import itertools
>>> l = [False, True]
>>> list(itertools.product(l, repeat=3))
[(False, False, False), (False, False, True), (False, True, False), (False, True, True), (True, False, False), (True, False, True), (True, True, False), (True, True, True)]
>>> 

And if you want the to change the tuples inside the list to sublists, try a list comprehension:

>>> import itertools
>>> l = [False, True]
>>> [list(i) for i in itertools.product(l, repeat=3)]
[[False, False, False], [False, False, True], [False, True, False], [False, True, True], [True, False, False], [True, False, True], [True, True, False], [True, True, True]]
>>> 

Answer 2

It's relatively easy if you consider the values to be bits instead. Like for the n = 3 case, see it as a value containing three bits.

Loop (using integers) from 0 to 2ⁿ - 1 (inclusive) and print all bits in each value (with 0 being False and 1 being True). Then you will have all permutations.

Of course, it's not a very Pythonic solution, but it's generic.

Answer 3

Try itertools.product with the repeat argument:

In [1]: from itertools import product

In [2]: product([True, False], repeat=2)
Out[2]: <itertools.product at 0x1c7eff51b40>

As you can see above, it returns an iterable, so wrap it in list():

In [3]: list(product([True, False], repeat=2))
Out[3]: [(True, True), (True, False), (False, True), (False, False)]

In [4]: list(product([True, False], repeat=3))
Out[4]:
[(True, True, True),
 (True, True, False),
 (True, False, True),
 (True, False, False),
 (False, True, True),
 (False, True, False),
 (False, False, True),
 (False, False, False)]

In [5]: list(product([True, False], repeat=5))
Out[5]:
[(True, True, True, True, True),
 (True, True, True, True, False),
 (True, True, True, False, True),
 (True, True, True, False, False),
 (True, True, False, True, True),
...

It also returns a list of tuples instead of a list of lists, but that should be fine for most use cases and can be solved very easily with a list comprehension if lists are really needed:

[list(tup) for tup in mylist]