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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
#!/usr/bin/env python3
from sys import argv, stdout
class Tableau:
def __init__(self, dim, maxmaxim, debug=False):
self.dim = dim
self.maxmaxim = maxmaxim # the largest sets to consider -- this is bogus
self.debug = debug
# Initialize the deck and its inverse map.
self.deck = []
self.index = {}
for i in range(3**self.dim):
card = self.int2card(i)
self.deck.append(card)
self.index[card] = i
# Initialize the deck of cards which have internal order.
# TODO: they should have pointers them in an array
# (see nextPartition)
self.deckOrdered = []
self.indexOrdered = {}
one, two = 0, 0
for i in range((self.dim + 1)*(self.dim + 2)//2):
# the (self.dim+1)'th triangular number
# is the number of internally ordered cards
card = ("1"*one + "2"*two).rjust(self.dim, "0")
self.deckOrdered.append(card)
self.indexOrdered[card] = i
if one == 0:
one, two = two + 1, 0
else:
one, two = one - 1, two + 1
# Initialize the deck of cards with internal order and no 2s.
self.deckOrderedNo2 = []
self.indexOrderedNo2 = {}
for i in range(self.dim + 1):
card = ("1"*i).rjust(self.dim, "0")
self.deckOrderedNo2.append(card)
self.indexOrderedNo2[card] = i
# Initialize the tableau and its state values.
self.tableau = [self.deck[0]]
self.becameBoundary = [0 for i in range(self.dim-1)]
# len(self.tableau) when the index became a boundary
# 0 means it has not become a boundary yet
self.brokeTransposes = 0
# len(self.tableau) when self.tableau[-1][0] first was nonzero
# 0 if it hasn't happened yet
self.noPop = True
def int2card(self, num):
if num != int(num):
raise Exception("Number must be an integer.")
if num < 0:
raise Exception("Number must be nonnegative.")
if num >= 3**self.dim:
raise Exception("Number must be less than {}.".format(3**self.dim))
strlist = []
for i in range(self.dim):
strlist.append(str(num%3))
num //= 3
return ''.join(reversed(strlist))
def card2int(self, card):
return self.index[card]
def nextPartition(self, partition, state):
"""Returns the next valid partition and carry bool.
This is where self.partitionState finally gets used.
(Which, indirectly, is when self.states gets used.)
The state is either the number of partitions before it,
or is None to indicate the partition may be freely incremented.
If there is no next partition in the lexicon,
then it zeros it out and returns True,
as a carry bit to increment the next partition.
"""
card = partition.rjust(self.dim, "0")
index = (self.index, self.indexOrdered, self.indexOrderedNo2)[state]
deck = (self.deck, self.deckOrdered, self.deckOrderedNo2)[state]
nextIndex = index[card] + 1
if nextIndex == len(deck):
carry = True
else:
nextCard = deck[nextIndex]
if len(partition) == self.dim:
carry = False
else:
carry = nextCard[-len(partition)-1] == "1"
if carry:
nextPartition = "0"*len(partition)
else:
nextPartition = nextCard[-len(partition):]
return nextPartition, carry
def nextCardWithPartitions(self):
nextCard = []
state = 1
boundaries = [index + 1 for index in reversed(range(self.dim - 1))
if self.becameBoundary[index] != 0]
boundaries = [self.dim] + boundaries + [0]
if self.debug:
print("boundaries:", boundaries)
for i in range(len(boundaries)-1):
stop, start = boundaries[i], boundaries[i+1]
partition = self.tableau[-1][start:stop]
if i == len(boundaries) - 2 and self.brokeTransposes == 0:
state = 2
nextPartition, carry = self.nextPartition(partition, state)
nextCard.append(nextPartition)
if not carry: break
else: return
if self.debug:
print("nextCard:", nextCard)
# nextCard = the attrs not incremented + the processed attrs
nextCard = self.tableau[-1][:boundaries[i+1]] \
+ "".join(reversed(nextCard))
return nextCard
def addCardWithPartitions(self, nextCard):
if self.brokeTransposes == 0:
if nextCard[0] == "1":
self.brokeTransposes = len(self.tableau) + self.noPop
elif nextCard[0] == "2":
raise Exception("First attribute must have value 1")
for index, addedWhen in enumerate(self.becameBoundary):
if addedWhen != 0:
continue
if nextCard[index] == nextCard[index + 1]:
continue
self.becameBoundary[index] = len(self.tableau) + self.noPop
self.tableau.append(nextCard)
def increment(self):
"""Appends the next appropriate card to tableau."""
if (self.brokeTransposes == 0) or (0 not in self.becameBoundary):
nextCard = self.nextCardWithPartitions()
if nextCard == None:
return False
self.addCardWithPartitions(nextCard)
else:
nextIndex = self.card2int(self.tableau[-1]) + 1
if nextIndex == len(self.deck):
return False
self.tableau.append(self.deck[nextIndex])
if self.debug:
print("becameBoundary:", self.becameBoundary)
print("tableau:", self.tableau)
return True
def revertToLen(self, length):
"""Resets to the state when len(self.tableau) == length.
Reverts self.becameBoundary and self.brokeTransposes.
"""
for index, addWhen in enumerate(self.becameBoundary):
if addWhen > length:
self.becameBoundary[index] = 0
if self.brokeTransposes > length:
self.brokeTransposes = 0
def incrementWithPop(self):
"""Increments in a way to replace the last card in tableau.
Kind of gimmicky.
Sets all the partition variables as if the card had been popped,
then runs self.increment() without popping it,
then removes the card to pop afterwards."""
self.noPop = False
if self.debug:
print("length:", len(self.tableau) - 1)
self.revertToLen(len(self.tableau) - 1)
while not self.increment():
del self.tableau[-1]
if len(self.tableau) == 1:
exit() # Iteration Complete
self.revertToLen(len(self.tableau) - 1)
del self.tableau[-2]
self.noPop = True
def main(self, outfile=stdout):
while True:
while self.increment():
self.print(outfile)
while len(self.tableau) == self.maxmaxim:
self.incrementWithPop()
self.print(outfile)
self.incrementWithPop()
self.print(outfile)
def print(self, outfile=stdout):
outstr = "[" + " ".join(self.tableau) + "]"
print(outstr, file=outfile)
def main():
if len(argv) <= 1: dim = 4
if len(argv) > 1: dim = argv[1]
if len(argv) <= 2: maxmaxim = 4
if len(argv) > 2: maxmaxim = argv[2]
outfile = open("generator.out", "w")
tableau = Tableau(dim, maxmaxim)
tableau.main(outfile)
if __name__ == "__main__": main()
|
