Construct power sets

An example for this behaviour is the calculation of power sets (sets of monomials/polynomials containing each term in the specified variables). The following code constructs such a power set very inefficiently for the first three variables:
sum([x(1)**i1*x(2)**i2*x(3)**i3 for i1 in (0,1) for i2 in (0,1) for i3 in (0,1)])
The algorithm has of course exponential complexity in the number of variables. The resulting ZDD however has only as many nodes as variables. In fact it can be constructed directly using the following function (from specialsets.py).
def power_set(variables):
    variables=sorted(set(variables),reverse=True,key=key)
    res=Polynomial(1).set()
    for v in variables:
        res=if_then_else(v,res,res)
    return res
Note, that we switched from polynomials to Boolean sets. We inverse the order of variable indices for iteration to make the computation compatible with the principles in [*] (simple ite operators instead of complex operations in each step).



2010-09-14