#!/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()