Problem 71c. Combinations.

Part I. Given the set S = { 1, 2, 3, ... , n }, and an integer r, with 0 <= r <= n. List all combinations of the set S taken r at a time in lexicographic order, and numbered. For example, if n = 5, and r = 3, then the combinations in lexicographic order are:

1. 1 2 3
2. 1 2 4
3. 1 2 5
4. 1 3 4
5. 1 3 5
6. 1 4 5
7. 2 3 4
8. 2 3 5
9. 2 4 5
10. 3 4 5

Notice that the combinations are numbered in sequence from 1 to C(n, r).

Input. The values of n and r.

Output. A listing like above.

Part II. Given a sequence number k, where 1 <= k <= C(n, r), find the corresponding combination.

Input. The value of k.

Output. The actual combination corresponding to the sequence number k.

Part III. Given a combination a_1 a_2 a_3 ... a_r, find the corresponding sequence number,

Input. The combination of r numbers.

Output. The corresponding sequence number k.