Generating All the Catalan Sequences

Given \(N\), how do I generate all the valid push/pop sequences (or draw all the trees)?

I’ll generate the sequence of 1’s and 0’s.

Start with the “smallest”: 101010

To get the next one, scan from the right till you see a 1 followed by a 0. Swap these two, and “reset” everything on the left. As an example:

10111000 becomes 11001010.

The “reset” means to just put alternating 1’s and 0’s from the end, but taking care to ensure the number of 1’s overall stays constant.

The messy code below does this. It also generates all the binary trees:

def next_seq(seq):
    prev_1 = False
    count1 = 0
    index = len(seq) - 1
    swap = False
    value = seq[-1]
    while index >= 0:
        value = seq[index]
        if value == 1:
            prev_1 = True
            count1 += 1
            index -= 1
            continue
        if not prev_1:
            index -= 1
            continue
        swap = True
        break
    if not swap:
        raise StopIteration
    seq[index] = 1
    seq[index + 1] = 0
    count1 -= 1
    index2 = len(seq) - 1
    while index2 > index + 1:
        seq[index2] = 0
        if index2 - 1 > index + 1:
            if count1:
                seq[index2 - 1] = 1
            else:
                seq[index2 - 1] = 0
        index2 -= 2
        count1 -= 1
    return seq


def get_all_sequences(N):
    seqs = []
    first_sequence = []
    for counter in range(2*N):
        if counter % 2 == 0:
            first_sequence.append(1)
        else:
            first_sequence.append(0)
    seqs.append(first_sequence)
    while True:
        try:
            seqs.append(next_seq(seqs[-1][:]))
        except StopIteration:
            break
    return seqs


def create_tree(sequence):
    """Sequence is a list of 1's and 0's with an equal number of 1's and 0's."""
    bt = BinaryTree()
    stack = []
    stack.append(bt)
    for entry in sequence:
        if entry == 1:
            stack.append(BinaryTree())
        else:
            r = stack.pop()
            l = stack.pop()
            stack.append(BinaryTree([l, r]))
    return stack.pop()


seqs = get_all_sequences(4)
trees = [create_tree(seq) for seq in seqs]

for seq, tree in zip(seqs, trees):
    print(seq)
    print()
    print(tree._ascii_art_())
    print()
    print()

[1, 0, 1, 0, 1, 0, 1, 0]

      o
     /
    o
   /
  o
 /
o


[1, 0, 1, 0, 1, 1, 0, 0]

    o
   / \
  o   o
 /
o


[1, 0, 1, 1, 0, 0, 1, 0]

    o
   /
  o
 / \
o   o


[1, 0, 1, 1, 0, 1, 0, 0]

  _o_
 /   \
o     o
     /
    o


[1, 0, 1, 1, 1, 0, 0, 0]

  o
 / \
o   o
     \
      o


[1, 1, 0, 0, 1, 0, 1, 0]

    o
   /
  o
 /
o
 \
  o


[1, 1, 0, 0, 1, 1, 0, 0]

  _o_
 /   \
o     o
 \
  o


[1, 1, 0, 1, 0, 0, 1, 0]

  o
 /
o
 \
  o
 /
o


[1, 1, 0, 1, 0, 1, 0, 0]

  o
   \
    o
   /
  o
 /
o


[1, 1, 0, 1, 1, 0, 0, 0]

o
 \
  o
 / \
o   o


[1, 1, 1, 0, 0, 0, 1, 0]

  o
 /
o
 \
  o
   \
    o


[1, 1, 1, 0, 0, 1, 0, 0]

o
 \
  o
 /
o
 \
  o


[1, 1, 1, 0, 1, 0, 0, 0]

o
 \
  o
   \
    o
   /
  o


[1, 1, 1, 1, 0, 0, 0, 0]

o
 \
  o
   \
    o
     \
      o