Generating noncrossing partitions in python

I want to generate all noncrossing partitions of a set S= [1,2,3,4,...,n], where a noncrossing partition is a partition where there does not exist elements a < b < c < d where a,c are in the same block, and b,d are in the same but different block.

Can somebody help me with this?

I have an algorithm that does this, but it works very slow, and I get a memory error when trying to calculate the noncrossing partitions on the set S= [1,2,3,4,...,14].

I've created a fairly heavily optimized implementation below. Note that it mutates partition lists (in the name of speed), so you will either need to use the partitions as they are produced, or deepcopy them. It will be noticeably faster to do the former, so opt for that if possible.

def make_partitions(elements):
    yield from _make_partitions(sorted(elements, reverse=True), [], []) 

def _make_partitions(elements, active_partitions, inactive_partitions):
    if not elements:
        yield active_partitions + inactive_partitions
        return

    elem = elements.pop()

    # Make create a new partition
    active_partitions.append([elem])
    yield from _make_partitions(elements, active_partitions, inactive_partitions)
    active_partitions.pop()

    # Add element to each existing partition in turn
    size = len(active_partitions)
    for part in active_partitions[::-1]:
        part.append(elem)
        yield from _make_partitions(elements, active_partitions, inactive_partitions)
        part.pop()

        # Remove partition that would create a cross if new elements were added
        inactive_partitions.append(active_partitions.pop())
    
    # Add back removed partitions
    for _ in range(size):
        active_partitions.append(inactive_partitions.pop())

    elements.append(elem)

Usage:

for partitions in make_partitions([1, 2, 3, 4, 5]):
    print(partitions)

Output:

[[1], [2], [3], [4], [5]]
[[1], [2], [3], [4, 5]]
[[1], [2], [3, 5], [4]]
[[1], [2, 5], [4], [3]]
[[1, 5], [4], [3], [2]]
[[1], [2], [3, 4], [5]]
[[1], [2], [3, 4, 5]]
[[1], [2, 5], [3, 4]]
[[1, 5], [3, 4], [2]]
[[1], [2, 4], [5], [3]]
[[1], [2, 4, 5], [3]]
[[1, 5], [3], [2, 4]]
[[1, 4], [5], [3], [2]]
[[1, 4, 5], [3], [2]]
[[1], [2, 3], [4], [5]]
[[1], [2, 3], [4, 5]]
[[1], [2, 3, 5], [4]]
[[1, 5], [4], [2, 3]]
[[1], [2, 3, 4], [5]]
[[1], [2, 3, 4, 5]]
[[1, 5], [2, 3, 4]]
[[1, 4], [5], [2, 3]]
[[1, 4, 5], [2, 3]]
[[1, 3], [4], [5], [2]]
[[1, 3], [4, 5], [2]]
[[1, 3, 5], [2], [4]]
[[1, 3, 4], [5], [2]]
[[1, 3, 4, 5], [2]]
[[1, 2], [3], [4], [5]]
[[1, 2], [3], [4, 5]]
[[1, 2], [3, 5], [4]]
[[1, 2, 5], [4], [3]]
[[1, 2], [3, 4], [5]]
[[1, 2], [3, 4, 5]]
[[1, 2, 5], [3, 4]]
[[1, 2, 4], [5], [3]]
[[1, 2, 4, 5], [3]]
[[1, 2, 3], [4], [5]]
[[1, 2, 3], [4, 5]]
[[1, 2, 3, 5], [4]]
[[1, 2, 3, 4], [5]]
[[1, 2, 3, 4, 5]]

As mentioned, if you need to preserve the partitions, you need to deepcopy them:

from copy import deepcopy

results = [deepcopy(partitions) for partitions in make_partitions(list(range(6)))]

On my machine, this can produce all non-crossing partitions of a set of 14 distinct elements in just a couple seconds.

Explanation

I generate each partition by considering of each possibility:

• create a new partition for it
• add it to an existing partition (for each)

Since I do this recursively, and in consistent element order, it would enumerate all partitions of the set.

However, I skip the crossing partitions by dropping (making inactive) any partitions containing elements larger than the elements already present in the partition we choose to add the new element to. So, if one partition has [1, 2] and another has [3], and we add 4 to the first partition, I would drop the [3] partition, because adding any elements greater than 4 would create a crossing partition (and since we're adding elements in increasing order, all future elements we can add to this partition would do so).

I optimize this step by implicitly ordering the active partitions in increasing order, so I can just remove the offending elements from the end. I also iterate over the partitions to add the new element to in reverse order, so I can incrementally remove offending partitions (ones that would cross in the future), one by one. This is why I only need to pop one element each time.