enum4mixedRadix.py~

#!/usr/bin/python
# This version of the program tries to solve the "surjective enumeration" problem with the order of
# the loops reversed from what we first envisioned. The inner loop will be over colors (traversing
# up and down the "tree") the outer loop will be over configurations for each color.
import sys
from tree import Tree
from msgenum import integer2coloring, coloring2integer

colors = [4,2,2] # Number of each color in the list
#t = Tree(colors)

# Make an empty list of groups, one list for each color
G = [[] for ilc in range(t.k)]

[G[0].append(i) for i in [[2,3,4,5,6,7,0,1],[2,3,0,1,4,5,6,7]]]
#G[0].append([(i+1)%t.n for i in range(t.n)])
growing = True
while growing:
    growing = False
    nG = len(G[0])
    for iG in G[0][:nG]:
        for jG in G[0][:nG]:
            g = [iG[i] for i in jG]
            if not g in G[0]:
                G[0].append(g)
                growing = True

survivors = []
config = [0]*len(colors)
ic = 0
nc = reduce(lambda x,y:x*y, colors)
limit = [ilc-1 for ilc in colors]
while config != limit and ic < nc:
    ic += 1
    # Construct the current labeling, all colors up to this depth
    labeling = t.coloring
    # Apply the permutations to the labeling, check index of each whether
    # idx < cIdx. If so, current coloring is a symmetric duplicate
    # Also collect the stabilizer while iterating over the group
    # elements
    print "<<<location: ",t.loc
    for ig in G[t.depth]: # Don't skip the identity, we need it at the next depth
        rlabeling = [labeling[ilc] for ilc in ig]
        # Now we need to reduce the coloring to zeros and current color only so that we can use the
        # coloring2integer routine
        if rlabeling == labeling: # current group operation is a member of the stabilizer
            G[t.depth+1].append(ig) # Add this group element to the stabilizer for the next depth
            print ig, "added to stabilizer"
        short = []
        for i in rlabeling:
            if i==t.depth+1: # i.e., the current color
                short.append(1)
            elif i==0:
                short.append(0)
        rIdx = coloring2integer(short)        
#        print "rIdx",rIdx,"short",short
        if rIdx < t.ccIdx: # Then we've hit this coloring before. Exit.
            print "found duplicate"
            t.decrement_depth()
            G[t.depth+1] = []             # Need to reset the stabilizer too
            break
    else: # This is a surviving coloring. If we are at the bottom of the tree, then it is a complete
          # labeling and should be added to the survivor list.
        if t.depth == t.k-2: # Add current coloring to the surivor list.
            survivors.append(t.loc[:])
            G[t.depth+1] = []             # Need to reset the stabilizer too
#        print "stabilizer:", G[t.depth+1]
    if t.loc == [-1]*t.k: # We are at the very end of the tree. We're all done
        break
    # If we are on the last branch at this layer we don't want to increment to the next node (why not?)
    if t.ccIdx <= rIdx: # current color index 
        print "incrementing: ccInd",t.ccIdx,
        t.increment_location()


#    else: # This was the last branch at this level and we need to reset the stabilizer too
#        print "clearing the stabilizer"
#        G[t.depth+1] = []
                                                  
for i,iSurv in enumerate(survivors):
    print "%s"%iSurv,
    if i < len(survivors) -1:
        if survivors[i][0] != survivors[i+1][0]:
            print 
print "\n"
print "number of survivors:",len(survivors)
if sys.argv[1] == "ps":
    for i in survivors:
        print i
#
#import matplotlib
#import matplotlib.pyplot
#
#cfig = matplotlib.pyplot.figure(figsize=[8.5,11])
#matplotlib.pyplot.subplots_adjust(left=0.001,right=.999,top=.999,bottom=.001)
#c = cfig.add_subplot(111)
#c.set_xlim([0,1000])
#c.set_ylim([0,1000])
#c.invert_yaxis()
#c.set_axis_off() # This gets rid of the coordinate ax
#c.set_aspect("equal")
#
#textdict = {"ha" :"center",
#            "va" : "center",
#            "size" : 12,
#            "fontname" : "Arial",
#            "zorder" : 1}
#
#pink = [1,.7,.7]
#lightblue = [.8,.9,1]
#lightgray = [.9,.9,.9]
#darkgray = [.7,.7,.7]
#
#xoffset = 10
#radius = 10
#xspacing = 2*radius*1.2
#colors = {1:"red", 2:"yellow", 3:"green", 0:"cyan"}
#yspacing = 2*radius*1.4
#yoffset = 10
#yiter = yoffset
#xiter = xoffset
#for j,iSurv in enumerate(survivors):
#    t.loc = iSurv
#    labeling = t.coloring
#    if yiter > 950:
#        yiter -= 33*yspacing
#        xiter += xspacing*t.n+5*xoffset
#    else:
#        yiter += yspacing
#        
#    for i in range(t.n):
#        fc = colors[labeling[i]]
#        p = matplotlib.patches.Circle([i*xspacing+xiter,yiter],radius,fc=fc,ec=[0.5,0.5,0.5],linewidth=.1,zorder=0)
#        c.add_patch(p)
#    c.text(xiter-xspacing,yiter,str(j+1),**textdict)
#
##c.text(0,0,"HERE",**textdict)
#
#cfig.savefig("perms.pdf",bbox_inches="tight")