<[EMAIL PROTECTED]> wrote: > [snipped] > > Do you know some algorithm (or you can give some suggestions) to > minimize the number of simple assignments needed for a "regular" > situation like that?
You can formulate the task as a graph-theoretic problem by representing the set of assignments as a digraph G(V,E), where: - V = set(LHS) | set(RHS): the vertex set V is the union of all left and right hand side expressions. - E = set((v1,v2) for "v1 = v2" in assignments): there is an edge from v1 to v2 for every assignment v1=v2. Now, every edge v1->v2 where in-degree(v1)==0 corresponds to a safe assignment: v1 is not assigned to any RHS, so it can be overwritten. After the assignment, both v1 and the edge (v1,v2) can be removed, decrementing the in-degree of v2. This happens iteratively as long as there are nodes with zero in-degree. At this point, all remaining nodes have in-degree >=1 and they form one or more strongly connected components. Since no RHS occurs more than once*, the out-degree of every vertex is less than or equal to 1. Therefore, for every component Ci, |Vi| >= sum(out-degree(v) for v in Vi) == |Ei|. Since for a strongly connected component |Vi| <= |Ei|, the previous relationship is actually equality |Vi| == |Ei|. Thus each component is a simple cycle v[1]->v[2]->...v[n]->v[1]. You can break the cycle by introducing an auxiliary variable x in an arbitrary edge, say v[n]->v[1]. Then the following assignments can take place: x = v[1]; v[1] = v[2]; v[2] = v[3]; ...; v[n-1] = v[n]; v[n] = x So overall, you need just one auxiliary variable for each strongly component of G. HTH, George * More than one assignments with the same RHS [v=a, v=b] are useless since only the last has an effect. In any case, the useless assignments can be filtered out in the beginning. -- http://mail.python.org/mailman/listinfo/python-list
