[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()
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
More information about the Tutor
mailing list