[Tutor] request for sugestions on fragement of code for generating truth-tables

Brian van den Broek broek at cc.umanitoba.ca
Thu Apr 6 02:40:14 CEST 2006

Danny Yoo said unto the world upon 31/03/06 08:27 PM:
>>Then, the output is like so:
>> >>> atoms = ["a","b","c"]
>> >>> tvas = tva_dict_maker(atoms)
>> >>> display_tvas(tvas)
>>a:True	b:True	c:True
>>a:True	b:True	c:False
>>a:True	b:False	c:True
>>a:True	b:False	c:False
>>a:False	b:True	c:True
>>a:False	b:True	c:False
>>a:False	b:False	c:True
>>a:False	b:False	c:False
> Hi Brian,
> We might be able to take advantage of the recursive nature of this
> problem.
> I'll sketch out the idea and try to fight the temptation to write it out
> in full.  *grin* If you haven't encountered recursion before, please shout
> out and ask for more details.

Hi Danny and all,

thanks for the response and my apologies for the delayed reply. (No 
internet at home and end of academic term death-march conspired :-)

My first thought about how to tackle the problem was indeed to do it 
recursively. I got bogged down and ended up with the alternate 
approach I posted in the original post.

Your post got me to take another bash and I obtained a recursive 
solution. But, subject to the caveat that my recursive solution might 
well be non-optimal, the non-recursive approach seems a bit better to 
me. Opinions welcome :-)

My recursive solution:

def recursive_tva_dict_maker(atoms, recursed=False):

     tvas = [{atoms[0]:True}, {atoms[0]:False}]

     if atoms[1:]:
         temp = []
         rest = recursive_tva_dict_maker(atoms[1:], True)

         for r in rest:
             for tva in tvas:
                 new = tva.copy()
         tvas = temp

     if not recursed:  # if test seemed cheaper than pointless sorting
         tvas.sort(key = lambda x: [x[y] for y in sorted(x)], 

     return tvas

My non-recursive solution:

def tva_dict_maker(atoms):

      tvas = []
      val = False

      for k in range(2**len(atoms)):

      for i in range(len(atoms)):
          key = atoms[i]

          for j in range(2**len(atoms)):
              if j % ( len(tvas) / 2.0 ** (i+1) ) == 0:
                  val = not val

      return tvas

The two functions have identical output. I don't much care about time 
or resources, as atoms will in practice never be more than 4 or 5 
items long. (So, the recursive solution could be simplified by getting 
rid of the if guard on the sorting. That the ultimate output be so 
sorted is essential, however.)

I'm more concerned with style and clarity.


Brian vdB

More information about the Tutor mailing list