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.

@U9-Forward sorry, I'm not that good at wording things. I added another example. — Anonymous, Jan 06 '19 at 08:46
Are you sure this is permutation? A permutation is "each of several possible ways in which a set or number of things can be ordered or arranged". [True, True, True] is not a rearrangament of True and False values. — zabop, Jan 06 '19 at 08:54
@KM142646 and Zabop I would rather prefer to say "Cartesian product of the set {True, False}, n times with itself", I agree that the requested list of lists is not the same as the set of permutations of the set {True, False} (the permutation set has only 2 elements; {True, False} and {False, True}). — AmirHosein Sadeghimanesh, Apr 20 '20 at 09:18
These are **not permutations**. This is the Cartesian product of a list (`[True, False]`) with itself `n` times. — Karl Knechtel, Mar 02 '23 at 00:54

U13-Forward · Accepted Answer · 2021-01-26T01:12:27.683

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

score 8 · Answer 2 · answered Jan 06 '19 at 08:53

8

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.

answered Jan 06 '19 at 08:53

Some programmer dude

400,186
35
402
621

Wow, didn't even think one bit about using binary. Very interesting. – Anonymous Jan 06 '19 at 09:00
You've one me :D (Don't like that pun? Two bad) – GeeTransit Jan 06 '19 at 09:03

score 3 · Answer 3 · answered Jan 06 '19 at 08:54

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]

zabop · Answer 4 · 2019-01-06T09:09:33.753

2

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.

edited Jan 06 '19 at 09:09

answered Jan 06 '19 at 09:03

zabop

6,750
3
39
84

That's not best way. – U13-Forward Jan 06 '19 at 09:04
1

please share a better one, I am also interested – zabop Jan 06 '19 at 09:04
Look at mine then. It's simpler too :D – GeeTransit Jan 06 '19 at 09:05
1

I would think just `[list(elem) for elem in listTuples]` would convert it appropriately – Anonymous Jan 06 '19 at 09:05
2

@zabop in my answer. – U13-Forward Jan 06 '19 at 09:06
@KevinMoy I agree with you. – U13-Forward Jan 06 '19 at 09:06

score 1 · Answer 5 · answered Jan 06 '19 at 08:52

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

GeeTransit · Answer 6 · 2019-01-06T22:00:51.810

1

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

edited Jan 06 '19 at 22:00

answered Jan 06 '19 at 08:52

GeeTransit

1,458
9
22

1

SyntaxError at `(True for _ in range(length),` – iz_ Jan 06 '19 at 09:07
I've fixed it. Phew, that took a lil bit. – GeeTransit Jan 06 '19 at 09:11
1

Still SyntaxError, missing comma. – iz_ Jan 06 '19 at 09:11
This is why I'm supposed to be in bed right now :D So sleepy haha. – GeeTransit Jan 06 '19 at 09:12
1

last line should be: [list(r) for r in result], otherwise syntaxerror – zabop Jan 06 '19 at 09:14
So what you want is, imo: import itertools # library of magiclength = 3 # length of your wanted permutations length = 3 result = itertools.combinations( # combinations based on position [*[True, False] * length], # generates the items needed length # length of the wanted results ) [list(r) for r in result] – zabop Jan 06 '19 at 09:15
Even with the `r` typo fixed, [this prints something completely wrong and completely different from what you claim it prints](https://ideone.com/xZhOuz). – user2357112 Jan 06 '19 at 09:17
1

`combinations` is the wrong tool for this job. At best, you can get something that overgenerates combinations and uses `set` to fix things, which is still horribly inefficient comparing to using `product`. – user2357112 Jan 06 '19 at 09:19

Ralph Yozzo · Answer 7 · 2020-10-13T14:36:11.177

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]

Generate all length-n permutations of True/False?

7 Answers7