summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rwxr-xr-xgenerator.py206
1 files changed, 206 insertions, 0 deletions
diff --git a/generator.py b/generator.py
new file mode 100755
index 0000000..dd89f4f
--- /dev/null
+++ b/generator.py
@@ -0,0 +1,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) == 0:
+ 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()