-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathenum4treeApproach.py~
executable file
·190 lines (180 loc) · 7.05 KB
/
enum4treeApproach.py~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#!/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
### Could we make some headway on the restricted site problem (at least for spectators) by using
### groups that skipped those sites (left them unchanged)?
#colors = [4,2,2] # Number of each color in the list
colors = [4,2,2] # Number of each color in the list
t = Tree(colors)
# Construct the cyclic permutation group of order n
G = [[] for ilc in range(t.k)]
#group[0]=[range(t.n)]
#i = 1
##print "element 0,0",[j for j in group[0][0]]
#for i in range(1,t.n):
# group[0].append([(j+i)%t.n for j in group[0][0]])
generators = [[1,2,0,4,5,3,7,8,6],[3,1,2,6,4,5,0,7,8],[1,0,2,3,4,5,6,7,8]]
generators = [[2,3,4,5,1,7,8,9,10,6],[2,1,3,4,5,7,6,8,9,10]]
generators = [[j -1 for j in i] for i in [[2,3,4,5,1,7,8,9,10,6],[2,1,3,4,5,7,6,8,9,10]]]
#print generators
#[G[0].append(i) for i in generators]
[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) for i in [[1,2,3,4,0,6,7,8,9 ,5],[1,0,2,3,4,6,5,7,8,9 ]]]
#G[0].append([(i+1)%t.n for i in range(t.n)])
#print G[0]
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)
#print g
growing = True
# print "Size of group",len(G[0])
g = len(G[0])
#for i,j in enumerate(G[0]):
# print i,j
##sys.exit()
survivors = []
t.increment_location(G)
ic = 0
while t.loc != [-1]*t.k:
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
# print "OUTER stabilizers",[len(ilc) for ilc in G]
# print "OUTER depth",t.depth
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.
# If you hit a duplicate, you want to go to the next branch *without*
# incrementing. Incrementing may take you _down_ the tree, but you want to do across in
# every case if you find a duplicate coloring. The problem with using the increment
# function is that it always goes down if it can. We don't necessarily want (or need) to
# traverse the entire tree. That's why below I compare the index of the current color to
# the rotated index.
# print "found duplicate"
#print "dup loc",t.loc
t.next_branch(G)
# print "dup loc",t.loc
#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[:])
# print "ADDED survivor:",t.loc
#G[t.depth+1] = [] # Need to reset the stabilizer too
# print "stabilizer N:", len(G[t.depth+1])
# print "depth",t.depth
# print "stabilizers",[len(ilc) for ilc in G]
# print "incrementing: ccInd",t.ccIdx
t.increment_location(G)
# print "after increment ****"
# print "stabilizer N:", len(G[t.depth+1])
# print "depth",t.depth
# print "stabilizers",[len(ilc) for ilc in G]
# print "*** location",t.loc
##WHY if t.loc == [-1]*t.k: # We are at the very end of the tree. We're all done
##WHY break
##WHY # If we are on the last branch at this layer we don't want to increment to the next node (why not?)
# if not rIdx < t.ccIdx:: # We only want to increment in the case that the current coloring was a survivory.
## print "incrementing: ccInd",t.ccIdx
##
## t.increment_location(G)
## print "after increment ****"
## print "stabilizer N:", len(G[t.depth+1])
## print "depth",t.depth
## print "stabilizers",[len(ilc) for ilc in G]
## print "*** location",t.loc
##
#nb = raw_input()
# 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[:t.k-1],
if i < len(survivors) -1:
if survivors[i][0] != survivors[i+1][0]:
print
print "\n"
print "Size of group",g
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")