algorithm - Calculate the index of a given number within a sorted set -

not sure if question should on math-overflow or here, try here first:

suppose given number n 1s , m 0s.

there (m+n)!/(m!*n!) different such numbers, can sorted in countable set.

for example, sorted set of numbers 2 ones , 3 zeros, is:

• 0 00011
• 1 00101
• 2 00110
• 3 01001
• 4 01010
• 5 01100
• 6 10001
• 7 10010
• 8 10100
• 9 11000

how can efficiently calculate index of given number within corresponding set?

note: input question only number, , not entire (corresponding) set.

let choose (n, k) = n! / k! / (n-k)!.

observe following structure of sorted set:

0 0|0011 1 0|0101 2 0|0110 3 0|1001 4 0|1010 5 0|1100 ------ 6 1|0001 7 1|0010 8 1|0100 9 1|1000

in sorted set, there choose (n + m, m) numbers (binary strings of length n + m) in total. first go numbers starting zero, , there choose (n + m-1, m-1) of them. go numbers starting one, , there choose (n-1 + m, m) of them. each of these 2 sections sorted.

so, if number b₁b₂...b_k starts 0 (b₁ = 0), index in sorted set same index of b₂...b_k in sorted set of binary strings of n ones , m-1 zeroes. if starts 1 (b₁ = 1), index in sorted set same index of b₂...b_k in sorted set of binary strings of n-1 ones , m zeroes, plus total number of binary strings starting zero, choose (n + m-1, m-1).

in way, recursively descent subproblems involving suffixes of original binary string, increasing sought number amount whenever meet 1. in end, come empty binary string 1 , string consisting of 0 zeroes , 0 ones.