Added generator.py to demo new iteration algorithm

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()