1234. Every Choice of k, Largest Member Last to Change

Print every subset of exactly k items from the items 1 to n, one per line, members in increasing order separated by single spaces, in this order:

> Subset A comes before subset B when the largest item belonging to exactly > one of them belongs to B.

That is called COLEX order. Equivalently, write each subset as its members in DECREASING order and sort those lists lexicographically.

n = 5, k = 3 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 2 3 5 1 4 5 2 4 5 3 4 5

## What most people try first

Print them in ordinary lexicographic order of their increasing member lists, which is what #1152 does and which would put 1 2 5 before 1 3 4. The two orders agree on the first four lines of the example above and disagree on the fifth, which is exactly the kind of difference that passes a small test.

The other instinct is to generate the subsets any way at all and then sort them by the colex rule. That works and it needs all C(n, k) of them in memory, and the sort key is the reversed member list, which is easy to get backwards.

## Why the order has to be pinned, and pinned without naming a program

A set of answers has no order. If a statement says only "print them all", two correct programs produce two different outputs and no automated check can tell a correct program from a broken one. So the order is part of the specification.

The second trap is pinning it as "the order your search finds them in". That names a program rather than a rule, and it is not a specification: a search that tries its options in a different sequence finds the same answers in a different order and is equally entitled to call itself correct. The rule below mentions no search.

## The useful property of colex order, and why it is the order worth knowing

Colex order does not depend on n. The first C(m, k) subsets of 1 .. n in colex order are exactly the subsets of 1 .. m in colex order, for every m between k and n, because a subset containing an item above m comes after every subset that does not. Ordinary lexicographic order has no such property: in lexicographic order the subsets of 1 .. m are scattered throughout.

So colex order lets a subset be numbered by a formula that does not mention n at all, which is why it is the order used whenever subsets have to be indexed. Lexicographic order is the order used whenever they have to be read by a human. Neither is more correct; they are for different jobs.

## Generating directly

Hold the subset as its members in increasing order and advance it like a counter:

start at 1, 2, 3, ..., k to advance: find the lowest position whose member can be increased by one without colliding with the member above it, or without passing n if it is the top increase that member by one reset every position below it to 1, 2, 3, ... if no position can be increased, the list is finished

That is the whole generator, and it is O(k) amortised per subset with no sorting and no memory beyond the current subset.

## Why that produces colex order

Increasing the member at position i and resetting everything below it leaves the members above position i unchanged. The largest item where the old and new subsets differ is therefore the one at position i, and the new subset has the larger value there, so the new subset comes after the old one by the rule. And no subset lies strictly between them: any subset agreeing with both above position i and having a larger member at i than the old one has at least the new one's value there, so it is at or after the new subset.

## The settled boundaries

k = 0 has exactly one subset, the empty one, and the statement says to print the word empty for it. k = n has exactly one subset, all of them. Both are tested, and so is n = 1 with k of 0 and 1.

## Cost

O(C(n, k) * k), which is the size of the output.

Constraints - `0 ≤ k ≤ n ≤ 10`