1166. Every Arrangement of k Out of n
Given n distinct integers and a number k, print every ARRANGEMENT of
exactly k of them: a sequence of k different values, where the order within
the sequence matters.
3 2
1 2 3 -> 1 2
1 3
2 1
2 3
3 1
3 2
Compare problem 1152, which asks for the SELECTIONS of size k and has three
answers here, since 1 2 and 2 1 are the same selection. Both appear in this
list because they are different arrangements.
## What most people try first
Produce every selection of size k and then every ordering of each. That is
correct, and it is two searches where one will do; it also tends to produce the
answers in the wrong order, grouped by selection, which is not the order asked
for.
The other common first move is to generate all n! full orderings and cut each
to its first k values. That is correct too, after deduplication, and it builds
n! leaves to produce n! / (n-k)! answers: at n = 8 and k = 2 that is
40320 leaves for 56 answers.
## The method
It is the ordering search of problem 1147 with the base case moved. Stop at
depth k instead of depth n:
go():
if size(cur) == k: record cur; return
for i in 0 .. n-1:
if used[i]: continue
used[i] = true; cur.push(a[i])
go()
cur.pop(); used[i] = false
Nothing else changes. The undo still has two halves, releasing the value and removing it from the sequence, and leaving either one out is the usual way this goes wrong.
## Why it is correct
Each call fills one position with any value not already used, so a leaf at depth
k is a sequence of k distinct values, which is an arrangement. Every
arrangement is reachable, because at each depth the value it wants is unused and
so is offered. No arrangement is produced twice, because two different leaves
differ at the first position where their paths diverged. Trying the values in
sorted order at every depth makes the leaves come out in the required order with
no sorting at the end.
## The output convention, shared by every problem in this block
Values inside one ordering are separated by single spaces, and orderings are
printed one per line. Two orderings are compared position by position
NUMERICALLY, and when one is a prefix of the other the shorter comes first. If
there are no orderings at all, print none.
## The settled boundaries
k = 0 has exactly one answer, the empty arrangement, printed as empty.
k > n has none, printed as none. k = n gives the full orderings, which is
problem 1147 exactly.
## Cost
There are n! / (n-k)! arrangements and the search does O(k) work per
arrangement, so the cost is proportional to the output. At n = 8 and k = 8
that is 40320 lines.
Constraints - `1 ≤ n ≤ 8` - `0 ≤ k ≤ 10` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.
Input
The first line contains two integers n and k.
The second line contains n space-separated distinct integers.
Output
Print every arrangement of exactly k of the values on its own line, values separated by single spaces, the lines ordered as described. Print empty for the empty arrangement and none if there are no arrangements.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.