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

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Thu Apr 6 23:38:24 CEST 2006


> 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!



More information about the Tutor mailing list