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]

Answer 4

And if you want list of lists, not list of tuples, start with U9-Forward's answer:

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

and continue:

lll=[]
for each in ll:
    lll.append([EACH for EACH in each])

lll will be a list of lists, instead of tuples.

---

Much better way, following comments:

[list(elem) for elem in lll]

Thanks to Kevin.

Answer 5

Here's a simple recursive list program

def list_exponential(n,set1=[]):
if n == 0:
    print(set1)
else:
    n-=1
    list_exponential(n, [False]+set1)
    list_exponential(n, [True]+set1)

list_exponential(5)

Sample output

$ python3 exponential.py 5
[False, False, False, False, False]
[True, False, False, False, False]
[False, True, False, False, False]
[True, True, False, False, False]
[False, False, True, False, False]
[True, False, True, False, False]
[False, True, True, False, False]
[True, True, True, False, False]
[False, False, False, True, False]
[True, False, False, True, False]
[False, True, False, True, False]
[True, True, False, True, False]
[False, False, True, True, False]
[True, False, True, True, False]
[False, True, True, True, False]
[True, True, True, True, False]
[False, False, False, False, True]
[True, False, False, False, True]
[False, True, False, False, True]
[True, True, False, False, True]
[False, False, True, False, True]
[True, False, True, False, True]
[False, True, True, False, True]
[True, True, True, False, True]
[False, False, False, True, True]
[True, False, False, True, True]
[False, True, False, True, True]
[True, True, False, True, True]
[False, False, True, True, True]
[True, False, True, True, True]
[False, True, True, True, True]
[True, True, True, True, True]

Answer 6

It is not efficient solution but you can use:

def permuteBool(n, l):
...      if n==0:
...         return l
...      return [permuteBool(n-1, l+[True])] + [permuteBool(n-1, l+[False])]
... 
>>> permuteBool(3, [])
[[[[True, True, True], [True, True, False]], [[True, False, True], [True, False, False]]], [[[False, True, True], [False, True, False]], [[False, False, True], [False, False, False]]]]

Answer 7

EDIT: Looks like I didn't check the output before posting my answer. It'll stay as it is as the right way would be a duplicate answer of the correct answer.

Use this simple code:

>>> import itertools  # library of magic
>>> length = 3        # length of your wanted permutations
>>> result = itertools.combinations(    # combinations based on position
...     [*[True, False] * length],      # generates the items needed
...     length                          # length of the wanted results
... )
>>> print([list(r) for in result])
[[False, False, False], [False, False, True], [False, True, False], [False, True, True], [True, False, False], [True, False, True], [True, True, False], [True, True, True]]