python build a dynamic growing truth table

Question

My question is simple: "how to build a dynamic growing truth table in python in an elegant way?"

for n=3

for p in False, True:
    for q in False, True:
        for r in False, True:
            print '|{0} | {1} | {2} |'.format(int(p),int(q), int(r))

for n=4

for p in False, True:
    for q in False, True:
        for r in False, True:
            for s in False, True:
                print '|{0} | {1} | {2} | {3}'.format(int(p),int(q), int(r), int(s))

I would like to have a function which takes n as a parameter and builds up the table, it is not necessary to print the table, returning a data structure representing the table is fine also.

score 53 · Accepted Answer · answered Jun 13 '11 at 21:14

53

Use itertools.product():

table = list(itertools.product([False, True], repeat=n))

Result for n = 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)]

answered Jun 13 '11 at 21:14

Sven Marnach

574,206
118
941
841

1

this is they way to go indeed. Thank you all for the answers. I will do it like here described, but the implementations under here are worth to look at and to vote up! – evildead Jun 13 '11 at 22:36

Glenn Moss · Answer 2 · 2011-06-20T17:58:40.127

List comprehensions are, of course, more Pythonic.

def truthtable (n):
  if n < 1:
    return [[]]
  subtable = truthtable(n-1)
  return [ row + [v] for row in subtable for v in [0,1] ]

Results, indented for clairity:

truthtable(1)
[ [0],
  [1] ]

truthtable(3)
[ [0, 0, 0],
  [0, 0, 1],
  [0, 1, 0],
  [0, 1, 1],
  [1, 0, 0],
  [1, 0, 1],
  [1, 1, 0],
  [1, 1, 1] ]

As a generator function with yield:

def truthtable (n): 
  if n < 1:
    yield []
    return
  subtable = truthtable(n-1)
  for row in subtable:
    for v in [0,1]:
      yield row + [v]

Also simply changing the return from an array comprehension to a generator expression makes the return type equivalent to the yield version's generator function:

def truthtable (n):
  if n < 1:
    return [[]]
  subtable = truthtable(n-1)
  return ( row + [v] for row in subtable for v in [0,1] )

how would it look like using yield? I'm kinda new in python. — evildead, Jun 13 '11 at 22:37

score 5 · Answer 3 · answered Jun 13 '11 at 21:27

5

itertools really is the way to go as has been pointed out by everyone. But if you really want to see the nuts and bolts of the algorithm required for this, you should look up recursive descent. Here's how it would work in your case:

def tablize(n, truths=[]):
    if not n:
        print truths
    else:
        for i in [True, False]:
            tablize(n-1, truths+[i])

Tested, working

Hope this helps

answered Jun 13 '11 at 21:27

inspectorG4dget

110,290
27
149
241

can you give me a version which uses yield? Would be very helpful for further problems :) I like yield in scala so much ;) – evildead Jun 13 '11 at 22:38

Tcll · Answer 4 · 2017-04-23T02:06:13.153

2

who here likes raw 1-liners?

>>> truthtable = lambda n: [[(v>>i)&1 for i in range(n-1,-1,-1)] for v in range(1<<n)] if n>0 else [[]]

100% tested and working.
(can't copy/paste result, or above code, cause I'm on a phone for Internet)

edited Apr 23 '17 at 02:06

answered Apr 23 '17 at 01:56

Tcll

7,140
1
20
23

1

tip: if you want yield-like functionality, just replace all brackets (except after else) with parentheses, the lambda function will then return a double generator object. – Tcll Apr 23 '17 at 02:15

Maviles · Answer 5 · 2020-09-23T20:18:47.070

2

Easy math aproach:

a = lambda x: [x//4%2,x//2%2,x%2]

for i in range(8):
    print(a(i))

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

EDIT:

A more general format wold be:

def truth_table(n):
    for i in range(2**n):
        line = [i//2**j%2 for j in reversed(range(n))]
        print(line)

This will only print the result as:

>>> truth_table(3)
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

edited Sep 23 '20 at 20:18

answered Feb 03 '20 at 20:58

Maviles

3,209
2
25
39

This is not a generalization, it will only work for n = 3 – Hans Sep 23 '20 at 05:44
1

here you go, try now – Maviles Sep 23 '20 at 21:22

score 2 · Answer 6 · answered Jun 13 '11 at 21:17

2

Have a look at the itertools module

In [7]: [i for i in itertools.product([0,1], repeat=3)]
Out[7]: 
[(0, 0, 0),
 (0, 0, 1),
 (0, 1, 0),
 (0, 1, 1),
 (1, 0, 0),
 (1, 0, 1),
 (1, 1, 0),
 (1, 1, 1)]

answered Jun 13 '11 at 21:17

Fredrik Pihl

44,604
7
83
130

Whatang · Answer 7 · 2017-05-15T21:11:34.580

returning a datastructure representing the table is fine

...in that case range(2 ** n) is all you need. Each number in the range represents a row in the truth table. The ith bit of the binary representation of the number k is 1 if and only if the ith variable is true in the kth row of the table.

If you want an actual table you can use:

[ [ ((row >> bit_index) & 1) == 1 for bit_index in range(n)] 
  for bit_index in range(2 ** n) ]

score 0 · Answer 8 · answered Apr 30 '21 at 06:53

Here's an implementation that uses functional programming, doesn't use loops, and doesn't import any external libraries:

get_bits = lambda n: [*map(lambda x:[*map(int,bin(x)[2:].zfill(n))],range(2**n))]

Then call get_bits with the desired number of parameters:

>>> get_bits(3)
[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 0],
 [0, 1, 1],
 [1, 0, 0],
 [1, 0, 1],
 [1, 1, 0],
 [1, 1, 1]]

Check out my GitHub repo to see my fleshed-out project for generating Truth Tables from boolean expression strings.

python build a dynamic growing truth table

8 Answers8

Linked