Algorithm lovers: how to build a constructive bijection between natural numbers and sets of k numbers from n?

Question

Combinatorics

There are numbers from 0 to n-1. It is necessary to enumerate all unique (up to permutation) sets of them by k numbers, k<n. And get a set by number with time complexity O(1). Memory is also O(1).
Example: n=6, k=4, sets C(n,k)
0 -> 0123
1 -> 0124
2 -> 0125
3 -> 0134
3 -> 0135
4 -> 0145
5 -> 0234
6 -> 0235
7 -> 0245
8 -> 0345
9 -> 1234
10 -> 1235
11 -> 1245
12 -> 1345
13 -> 2345

Answer 1

It seems to me that it will be enough to add 1 using addition modulo n.

Answer 2

And what's the problem with creating your own Map implementation, which will have the add () method reimplemented: the number as a string, it as a charArray, then sort and add.

Answer 3

It seems to me that getting O (1) will not work either for n or for k. Because already to get the first digit by number, you need to be able to determine in which of the intervals of the form (f(n,k,x),g(n,k,x)] this number lies, where f(n,k,x) = C(nx-1,k-1), g(n,k,x) = f(n,k,x)+C(nx-2,k-1).

Answer 4

There are ready-made ways of numbering combinations, by the way. The set of combinations is recursively divided into parts, the power of which is known, the number is also formed recursively. I can't explain in detail, I don't understand it myself :) I look in Romanovsky 's Discrete Analysis , p. fifty.

Answer 5

This is done by dynamic programming in O(nk) complexity in CPU and memory.

Answer 6

ON THE NUMBERING OF PERMUTATIONS AND COMBINATIONS FOR ORGANIZATION...