diff options
| -rwxr-xr-x | generator.py | 206 |
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() |