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

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}，它将返回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个字符串。No d（“ aabee”）：E（0，2，6）= 6No e（“ aabff”）：E（0，2，5）= 5No 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; 
   }