Print all partitions into disjoint combinations of fixed size

Question

I have an array of numbers from 1 to n, and I need to find all possible partitions into disjoint combinations of 3 numbers.

That is, for n = 9 the situation is as follows:

Array: 1, 2, 3, 4, 5, 6, 7, 8, 9;

Possible combinations of 3: 123, 124 ... 245, 246 ... 478, 479, etc .;

Possible partitions into 3 disjoint combinations: 123 456 789, 123 457 689 ... 123 468 579 ... 127 458 369, etc.

I've found an algorithm for finding combinations of 3 numbers from a set, here it is: https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n / (there are even 2 of them, but I used the first one). Now the question is how to find combinations of the combinations themselves, and this already causes difficulties: it seems to me that for this I need to deal with recursion again, but how and where exactly to use it, I don't fully understand (and perhaps the point is then another). Also I've seen a non-recursive algorithm that finds all the combinations from given numbers, https://rosettacode.org/wiki/Combinations#C.23, but could do nothing with it (I enclose my work with it). Could you please help me?

public static IEnumerable<int[]> Combinations(int[] a, int n, int m)
        {
            int[] result = new int[m];
            Stack<int> stack = new Stack<int>();
            stack.Push(0);
            while (stack.Count > 0)
            {
                int index = stack.Count - 1;
                int value = stack.Pop();
                while (value < n)
                {
                    result[index++] = ++value;
                    stack.Push(value);
                    if (index == m)
                    {
                        for (int i = 0; i < 3; i++)
                        {
                            a = a.Where(val => val != result[i]).ToArray();
                        }
                        return Combinations (a, n-3, m);
                        break;
                    }
                }
            }
        }

Answer 1

Assuming n is a multiple of 3, there is a simple and intuitive recursive algorithm. (Writing it efficiently is a bit more of a challenge :-) ).

In pseudocode, generalising 3 to k:

# A must have a multiple of k elements
# I write  V \ C to mean "V without the values in C". Since producing
# copies is expensive, you should find a more efficient way of doing
# this.
Partition(A, k):
    If A has k elements, produce the partition consisting only of A
    Otherwise:
        Let m be the smallest element of A. 
        For each combination C of k-1 elements from A \ [m]:
            Add m to C
            For each partition P generated by Partition(A \ C, k):
                produce P with the addition of C

Of course, that depends on you having access to an algorithm which can enumerate the k-combinations of a list. (Even better would be a function which produced successive shuffles of the list with different k-combinations at the beginning, while maintaining the list in order. Sadly, few standard libraries provide that.)

There's another recursive algorithm, which can easily be made into an iterative algorithm by maintaining an explicit stack. It's possibly not quite as intuitive, although once you see it, how it works is pretty obvious, but it's a lot easier to implement efficiently. It requires us to maintain the invariants that each set in the partition is stored in increasing order, and that the sets themselves are sorted in increasing order by their first element. (The order itself is irrelevant, and it's totally reasonable to just assume that the the original order of the elements is the desired sortation, as long as the elements are kept in a data structure whose ordering is constant.)

Once you establish that rule, you can start by making all the partition's sets empty, and then place each successive element in order, using each of the possible locations which obey the following simple constraints:

1. Once a set contains the correct number of elements, no more elements can be added to it.
2. Each element is placed at the end of a set (because all the already-placed elements are smaller and all the elements yet to be placed are bigger);
3. An element can only be added to an empty set if it is the first empty set in the partition (to guarantee that the sets themselves will be sorted).

To avoid constantly copying the sets in the partition, you can implement this by using a fixed-size two-dimensional array of k rows and n ⁄ k columns, where each row represents one set in the partition; it's then necessary to keep another array of n ⁄ k integers the current length of each set.

---

One advantage of the first algorithm is that it makes it reasonably obvious how many possible partitions there are, because the number of partitions generated by the inner loop is independent of the combination chosen in the outer loop. Consequently, if we write P(n, k) for the number of k-partitions of n objects, we can see that

P(n, k) = C(n−1, k−1) × P(n−k, k) for n>0   (where C(n, k) is the binomial coefficient)

That's simply a product of binomial coefficients:

P(n, k) = C(n−1, k−1) × C(n−k−1, k−1) × C(n−2k−1, k−1) × … × C(k−1, k−1)

Since C(n, k) is n! ⁄ k!(n−k)!, that can be simplified to n! ⁄ (d! × k!^d) where d is the number of sets in each partition, i.e. d = n ⁄ k. That number is obviously a lot smaller than n! but it still grows extremely rapidly, making large arguments to the partition function impractical. For k=3, the first few counts are:

P( 3, 3) = 1
P( 6, 3) = 10
P( 9, 3) = 280
P(12, 3) = 15,400
P(15, 3) = 1,401,400
P(18, 3) = 190,590,400
P(21, 3) = 36,212,176,000

For this reason, it's usually advisable to generate and use the possible values one at a time rather than attempting to stash them all into a massive vector, which would take up a lot of memory.