计算有序集合中给定数字的索引

Question

不确定这个问题是否应该在Math-Overflow或这里,所以首先尝试这里:

假设我们给出一个N 1和M 0的数字.

存在(M + N)!/(M!*N!)个不同的这样的数字,可以在可数集合中进行排序.

例如,具有2个1和3个零的所有数字的有序集合是:

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

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

注意:此问题的输入只是数字,而不是整个(相应)集合.

Answer 1

我们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)它们.这两个部分中的每一部分也被排序.

因此,如果您数B ₁ b ₂.B _ķ具有零(B开始₁ = 0),其在有序集合索引是与B相同的索引₂.B _ķ在有序集合的所有二进制的N1和M-10的字符串.如果它以一个(b ₁ = 1)开头,则它在有序集合中的索引与所有二进制字符串1和0 的有序集合中的b ₂ ... b _k的索引相同,加上总数二进制字符串以零开头,即.N-1Mchoose (N + M-1, M-1)

通过这种方式,您递归下降到涉及原始二进制字符串后缀的子问题,每当遇到1时,将所需数量增加一些.最后,您得到一个空的二进制字符串,显然是唯一的字符串0个零和0个.

Answer 2

这称为组合算法中的排名.这是一个为您执行此操作的C函数:

unsigned long rank_choose(unsigned long n, unsigned long k, unsigned long c) {
  unsigned long res = 0;
  for (; n > 0; n--) {
    if (c & 1) { res += binomial(n-1, k); k--;}
    c >>= 1;
  }
  return res;
}

它假设您有一个binomial(n, k)计算系数的函数n!/k!/(n-k)!.小心,我在这里提出的解决方案使用endianess反向表示:

const int m = 5, n = 2;
int k = 12;
std::cout << std::bitset<m>(k) << " " << rank_choose(m, n, k) << std::endl;
k = 9;
std::cout << std::bitset<m>(k) << " " << rank_choose(m, n, k) << std::endl;

返回:

01100 2
01001 7

这是另一个endianess的解决方案:

unsigned long rank_choose_rev(unsigned long n, unsigned long k, unsigned long c) {
  unsigned long res = 0, mask = 1<<(n-1);
  for (; n > 0; n--) {
    if (c & mask) { res += binomial(n-1, k); k--;}
    mask >>= 1;
  }
  return res;
}

然后

01100 5
01001 3

注意:下面的@Gassa很好地描述了这些算法(给他+1).