The big combination problem

Question

Since combination is based on binary selection, either you choose an element from a set or not, two options only 1 for choosed element or 0 not choosen

Example if 4C2 the first selection will be 0011, second 0101, third 0110 and so on. our selections follow the increase of binary number if you already know from my example.

Then my question is if we dont include empty selection meaning 0000 and counting the first selection, 0011, as one, two up to the end of possible combinations, for my example is 1100, is there a method or formula to calculate the nth possible combination in the order of increasing binary number? For computer may be by iteration of all possible combination by searching binary numbers

Will computer be able to do this, 2^101:+ 5 term of 509C58?

See this problem and this problem(the reverse of the other linked problem). See also wikipedia on combinatorial number systems — JMoravitz, Dec 20 '17 at 16:44
So what you seem to be looking for is a function that gets the $x^{\text{th}}$ integer such that it's binary representation is at most $n$ long and has exactly $k$ 1s? — Benji Altman, Dec 20 '17 at 16:48

score 1 · Answer 1 · answered Dec 20 '17 at 17:00

You are listing the $n \choose r$ binary words of length $n$ containing $r\ 1$s in lexicographic order. You can form your word of length $n$ either by writing a $0$ followed by a word of length $n-1$ with $r\ 1$s or by writing a $1$ followed by a word of length $n-1$ with $r-1\ 1$s. The first set should come before the second set. This is captured by the equation $${n \choose r}={n-1 \choose r}+{n-1 \choose r-1}$$ Given you want the $N$th word in the list, you can ask whether $N \gt {n-1 \choose r}$. If not, write a $0$ and you want the $N$th word in the list of words of length $n-1$ with $r\ 1$s. If so, write a $1$ and you want the $N-{n-1 \choose r}$th word in the list of words of length $n-1$ with $r-1\ 1$s.

As an example, take $n=10,r=5$ and say we want the $179$th word in the list of $10$ bit words with $5\ 1$s. ${9\choose 5}=126$ and $179 \gt 126$, so we start with a $1$ and look for the $179-126=53$rd word in the list of $9$ bit words with $4\ 1$s. The reason we subtracted $126$ is there are that many $10$ bit words starting with $0$. Now ${8 \choose 4}=70$ and $53 \lt 70$ so we write a $0$ and look for the $53$rd word of length $8$ with $4\ 1$s. ${7 \choose 4}=35$ so we write a $1$ and look for the $18$th word of length $7$ with $3\ 1$s and so on. Any package that can handle large integers can do this calculation for huge numbers.

The big combination problem

1 Answers1