1192. Every Split Into Exactly k Groups

There are n items, numbered 1 to n. Print every way to put them into exactly k groups, where every group holds at least one item and every item is in exactly one group.

4 items, k = 2 -> 1 1 1 2 item 4 alone 1 1 2 1 item 3 alone 1 1 2 2 {1,2} and {3,4} 1 2 1 1 item 2 alone 1 2 1 2 {1,3} and {2,4} 1 2 2 1 {1,4} and {2,3} 1 2 2 2 item 1 alone

Seven of them, which is the Stirling number of the second kind S(4, 2).

## What most people try first

Give each item a group number from 1 to k and keep the assignments that use all k numbers. That is k^n assignments, and every answer appears k! times in the result, because renaming the groups does not change the split. At n = 8, k = 4 that is 65536 assignments producing 24 copies of each of the 1701 real answers.

Worse than the waste is that the duplicates have to be removed, which means recognising when two assignments describe the same split. Doing that properly means computing a canonical form, and once you can compute the canonical form you may as well generate only canonical forms.

## The output convention, which is most of the problem

A split has no natural order. The split that puts items 1 and 3 together and item 2 alone is the SAME split however you name the groups, so {{1,3},{2}} and {{2},{1,3}} are one answer and not two. A search that picks a group for each item finds that one answer k! different ways unless something stops it.

So the printed form is fixed, and it is fixed in a way that admits exactly one spelling per split. Print one GROUP LABEL per item, in input order, separated by single spaces, under this rule:

• item 1 is always in group 1
• each later item is either in a group that some earlier item already uses, or
• in the next unused group number, and never in a higher one

That is the only labelling of a split obeying the rule, so two different lines are always two different splits, and no de-duplication is ever needed. Lines are printed in LEXICOGRAPHIC order, compared position by position, which is exactly what trying the labels in increasing order at every item produces.

## The method

go(i, used): # items before i are labelled, used groups open if i == n: if used == k: record cur return if used > k: return # too many groups already if used + (n - i) < k: return # not enough items left to open k for lab in 1 .. min(used + 1, k): cur.push(lab); go(i + 1, max(used, lab)); cur.pop()

Two bounds, and both are sound for the same reason: a group once opened is never closed, and each remaining item opens at most one new group. So used never decreases and can rise by at most one per item. If it is already above k the branch is dead, and if even opening a new group for every remaining item would not reach k, it is dead too.

## Why this is symmetry breaking and not formatting

The rule above is doing real work. Without it the search would reach the same split once per way of naming its groups, so it would do k! times too much work and print k! copies of every answer. Filtering the duplicates out afterwards would need every answer held in memory and compared, which is worse than not generating them.

Forbidding a label higher than one more than the largest used so far removes every duplicate AT THE SOURCE, before any work is spent below it. That is the cheapest kind of pruning there is: it is not a bound that might fail to fire, it is a restriction that makes each answer reachable exactly once.

## Why it is correct

The labelling rule and the splits are in one-to-one correspondence. Given a split, label its groups by the order of their smallest item: that labelling obeys the rule, and it is the only one that does, since the rule forces the label of each item as soon as the groups of the earlier items are fixed. Given a labelling obeying the rule, the groups of equal labels are a split. So the search, which generates every rule-obeying labelling exactly once, generates every split exactly once.

## The settled boundaries

k = 1 has one answer, every item in group 1. k = n has one answer, every item alone. k > n cannot happen because the constraints forbid it, and k = n and k = 1 are both tested. There is always at least one answer, so none is never printed by this problem; it is still specified for completeness.

## Overflow

The count of answers is S(n, k), which at n = 8 peaks at 1701. Nothing overflows and nothing needs a wide type. Problem #1197 counts the same splits at n = 20, where the count does pass 32 bits, and that is where the overflow discussion belongs.

## Cost

One node per rule-obeying prefix, so the work is proportional to the number of answers plus the pruned prefixes, and O(n) to print each answer.

Constraints - `1 ≤ k ≤ n ≤ 8`