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

[Brian van den Broek]

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()
                 new.update(r)
                 temp.append(new)
         tvas = temp

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

     return tvas

My non-recursive solution:

def tva_dict_maker(atoms):

      tvas = []
      val = False

      for k in range(2**len(atoms)):
          tvas.append(dict())

      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
              tvas[j][key]=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.

Best,

Brian vdB