如何获得给定组合的索引？

Question

我有一个数字数组序列，每个数组有 5 个元素，从 0 到 8，我必须订购而不是使用该组合，我的意思是：

i=0, {0,0,0,0,0}
i=1, {0,0,0,0,1}
i=2, {0,0,0,0,2}
i=3, {0,0,0,0,3}
i=4, {0,0,0,0,4}
i=5, {0,0,0,0,5}
i=6, {0,0,0,0,6}
i=7, {0,0,0,0,7}
i=8, {0,0,0,0,8}
i=9, {0,0,0,1,1}
     ...
i=1285, {7,8,8,8,8}
i=1286, {8,8,8,8,8}

所以如果我将 {0,0,1,1,2} 赋给函数，它就是 returns 7。我考虑过使用 Combinatorial number system 但我遗漏了一些我不知道是什么的东西，下面的代码不起作用

#include <stdio.h>
#include <stdlib.h>

#define size 1287

int combination[9][5] =     {
                    {0,  0,   0,      0,      0},
                    {1,  1,   1,      1,      1},
                    {2,  3,   4,      5,      6},
                    {3,  3,   6,     15,     21},
                    {4, 10,  20,     35,     56},
                    {5, 15,  35,     70,    126},
                    {6, 21,  56,    126,    252},
                    {7, 28,  84,    210,    462},
                    {8, 36, 120,    330,    792}
                };

int getKey(int array[]){
    int key=0;
    int tempArray[9] = {0};
    for(int i=0;i<5;i++){
        tempArray[array[i]]++;
    }
    int j=0;
    for(int i=0;i<9;i++){
        if(tempArray[i]!=0){
            while(tempArray[i]!=0){
                array[j++] = i;
                key += combination[i][5-j];
                tempArray[i]--;
            }
        }
    }
    return key;
}

int main(){
  int it[5];
  for(it[0]  = 0 ;it[0]<9;it[0]++){
    for(it[1]=it[0];it[1]<9;it[1]++){
      for(it[2]=it[1];it[2]<9;it[2]++){
        for(it[3]=it[2];it[3]<9;it[3]++){
          for(it[4]=it[3];it[4]<9;it[4]++){
            printf("{%d %d %d %d %d} = %d\n",it[0],it[1],it[2],it[3],it[4],getKey(it));
          }
        }
      }
    }
  }
  return 0;
}

Obs：我正在使用计数排序来保持字典顺序，理论上我会收到未排序的数组。

Answer 1

我会给你我为你昨天发布并删除的这个问题的前一版本写的答案。（顺便说一下，这是一种糟糕的形式。）

我们称二项式系数C(n, k) = n!/(k!(n-k)!)

从s个符号的字母表中抽取m个字母的无序串的个数为C(m+s-1,s-1)。我们称其为 D(m, s)。在这种情况下，D(5, 9) = C(5+9-1, 9-1) = C(13, 8) = 1287

让我们对每个字符串进行排序，然后编号：

aaaaa 1
aaaab 2
aaaac 3
...
aaaai 9
aaabb 10
aaabc 11
...

如果一个字符串包含5个a，它的个数是D(5, 1) = C(5+1-1, 1-1) = C(5, 0) = 1.
如果一个字符串包含 4 个 a，则它的数字是 1 加上由非 a 字母确定的数字，直到 D(1,8) = C(1+8-1,8-1) = C(8, 7) = 8。所以他们上升到 1+8=9。
如果一个字符串包含 3 个 a，它的数字是 9 加上一个由非 a 字母确定的数字，它上升到 D(2,8) = C(9,7) = 36，所以 9+36=45.
如果一个字符串包含 2 个 a，则其编号在 [46,165].
中如果一个字符串包含1个a，它的编号在[166, 495].
如果一个字符串不包含 a，则它的编号在 [496, 1287].

那么字符串 "aabgg" 呢？它的数量是(45)+(8)+(7)+(6)+(5)+(4)+(1)=76

没有碰撞，索引的计算是O(sm(s+m))，对于m=5和s=9来说还算不错。

编辑： 澄清一下，让我们定义

E(j, m, s) = D(0,s-1)+D(1,s-1)+...+D(m-j-1,s-1)

假设从s个符号的字母表中提取的m个字母组成的字符串包含字母表的第一个字母j。目录中有 E(j,m,s) 个字符串 在第一个这样的字符串之前。 例如，在第一个以两个 a 开头的字符串之前 ("aabbb") , 有 E(2, 5, 9)=45 个字符串。

要达到 "aabbb"，我们必须数出 45 个字符串。
要从 "aabbb" 到下一个恰好包含一个 b ("aabcc") 的字符串，我们必须计算出 E(1, 3, 8) = 8 个字符串。
从那里到下一个不包含 c ("aabdd") 的字符串，E(0, 2, 7) = 7 个字符串。
无 d ("aabee"): E(0, 2, 6) = 6
没有 e ("aabff"): E(0, 2, 5) = 5
无 f ("aabgg"): E(0, 2, 4) = 4
而且我们必须数 "aabgg" 本身：1

Answer 2

好吧，我认为这看起来像八月号 1...8

0 = {00000}
1 = {00001}
2 = {00002}
8 = {00010}

如果这是你的意思

我觉得这个算法最好

   int get_key(int a[5]){
      int idx, rval=0;
      for(i=4; i<=0; i--)
         rval += powl(a[i], i);
      return rval; 
   }

如何获得给定组合的索引？

How can I get the index of a given combination?

c

math

combinations

combinatorics

binomial-coefficients