计算给定数字在排序集中的索引

不确定这个问题应该在 Math-Overflow 上还是在这里，所以首先在这里尝试：

假设我们有一个包含 N 个 1 和 M 个 0 的数字。

有 (M+N)!/(M!*N!) 个不同的这样的数字，可以在可数集合中排序。

例如，包含 2 个 1 和 3 个 0 的所有数字的排序集为：

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

我们如何有效地计算给定数字在相应集合中的索引？

注意：该问题的输入是only数量，以及not整个（对应的）集合。

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

观察排序集的以下结构：

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

在有序集合中，有choose (N + M, M)数字（长度为二进制字符串N + M） 总共。 首先输入以零开头的数字，有choose (N + M-1, M-1)其中。然后从一开始的数字，有choose (N-1 + M, M)其中。这两个部分中的每一个也都已排序。

So, if your number b₁b₂...b_k starts with a zero (b₁ = 0), its index in the sorted set is the same as index of b₂...b_k in the sorted set of all binary strings of N ones and M-1 zeroes. If it starts with a one (b₁ = 1), its index in the sorted set is the same as index of b₂...b_k in the sorted set of all binary strings of N-1 ones and M zeroes, plus the total number of binary strings starting with a zero, which is choose (N + M-1, M-1).

通过这种方式，您可以递归地解决涉及原始二进制字符串后缀的子问题，每当遇到 1 时，就会将要查找的数字增加一定数量。最后，您会得到一个空的二进制字符串，它显然是唯一一个由以下内容组成的字符串： 0 个零和 0 个一。