Alternative solution for "5.15 Compute a random subset ", which avoid the use of extra auxiliary space, with O(k + n) time complexity and O(1) space complexity, in Python (September 2018 edition).

The idea here is to pick the r-th combination, and find its constituents by incrementing them in a odometer like fashion, and taking into account that the next digit in the combination will be greater than the previous one.

For example, the combination sequence for n=5 and k=2 is:

0 - [0,1]

1 - [0,2]

2 - [0,3]

3 - [0,4]

4 - [1,2]

5 - [1,3]

6 - [1,4]

7 - [2,3]

8 - [2,4]

9 - [3,4]

To know how many combinations exist for a given n/k, or to know how many combinations exist until the next digit change, the following formula is used: n!/((n - k)!k!)

## Algorithm to compute random subset

```
import random, math
def random_subset(n, k):
def num_combinations(n0, k0):
return math.factorial(n0) // (math.factorial(n0 - k0) * math.factorial(k0))
combination_idx = random.randint(0, num_combinations(n, k) - 1)
result = [0] * k
counter = 0
for k_i in range(k):
if (k_i > 0):
result[k_i] = result[k_i - 1] + 1
while (n - 1 - result[k_i] >= 0
and combination_idx >= counter + num_combinations(n - 1 - result[k_i], k - k_i - 1)):
counter += num_combinations(n - 1 - result[k_i], k - k_i - 1)
result[k_i] += 1
return result
```

Complete gist at: https://gist.github.com/lopespm/fe4d7fa8ac6331b2597c3d09f3a05b24