> 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
Hi Brian,
One way to get rid of the 'recursed' flag is to refactor slightly, and
break out the sorting in another helper function, like this:
##################################################################
def tva_dict_maker(atoms):
tvas = tiva_helper(atoms)
tvas.sort(key = lambda x: [x[y] for y in sorted(x)],
reverse=True)
return tvas
def tva_helper(atoms):
tvas = [{atoms[0]:True}, {atoms[0]:False}]
if atoms[1:]:
temp = []
rest = recursive_tva_dict_maker(atoms[1:])
for r in rest:
for tva in tvas:
new = tva.copy()
new.update(r)
temp.append(new)
tvas = temp
return tvas
##################################################################
This way, tva_helper() doesn't have to care about sorting, since
tva_dict_maker() will do it instead.
Here's a slightly wordier version of what you have, but taken to a far
extreme. *grin*
##################################################################
## In the comments below, an "assignment" is a dictionary
## that maps atoms to booleans.
def make_truth_table(atoms):
"""make_truth_table: (listof atoms) -> (listof assignment)
Builds a small truth table of all possibilities."""
if atoms == []:
## the empty case is one with the "empty" assignment!
return [{}]
else:
sub_assignments = make_truth_table(atoms[1:])
return (extend_all(sub_assignments, {atoms[0] : True}) +
extend_all(sub_assignments, {atoms[0] : False}))
def extend_all(assignments, extension):
"""extend_all: (listof assignment) assignment ->
(listof assignment)
Takes each assignment in the list of assignments, and
enhances it with the extension.
"""
return [extend_assignment(single, extension)
for single in assignments]
def extend_assignment(assignment, extension):
"""extend_assignment: assignment assignment -> assignment
Takes the assignment and creates a new one that extends the
first with the extension."""
extended = assignment.copy()
extended.update(extension)
return extended
##################################################################
As you can tell, I really like helper functions. *grin* I've tried to
document as best I can to make it clearer how the recursive approach
breaks things down.
[non-recursive code cut]
> 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.
Yes, I agree that the readability of the code is primary. Understandng
the recursive approach depends on the reader's comfort with recursive
functions, and the non-recursive code depends on the reader's comfort with
arithmetic operators.
Best of wishes to you!
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
