Как я могу получить индекс данной комбинации?

У меня есть последовательность массивов чисел с 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. Я подумал об использовании Комбинаторная система счисления, но я что-то упустил, я не знаю, что это такое, приведенный ниже код просто не работает

#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;
}

Наблюдения: я использую сортировку подсчетом, чтобы сохранить лексикографический порядок, теоретически я буду получать несортированные массивы.


c math combinations binomial-coefficients combinatorics
person NedLandy    schedule 12.05.2020    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я дам вам ответ, который я написал для предыдущей версии этого вопроса, который вы разместили вчера и удалили. (И это, кстати, дурной тон.)

Назовем биномиальный коэффициент C(n, k) = n!/(k!(n-k)!)

Количество неупорядоченных строк из m букв, составленных из алфавита из s символов, равно 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 букв "а", ее число равно D(5, 1) = C(5+1-1, 1-1) = C(5, 0) = 1.
Если строка содержит 4 буквы "а", ее число равно 1 плюс число, определяемое буквой, отличной от a, которая увеличивается до D(1,8) = C(1+8-1,8-1) = C(8, 7) = 8. Таким образом, они идут до 1+8=9.
Если строка содержит 3 буквы "а", ее число равно 9 плюс число, определяемое буквами, отличными от буквы "а", которое увеличивается до D(2,8) = C(9,7) = 36, поэтому 9+36= 45.
Если строка содержит 2 буквы "а", ее номер находится в [46,165].
Если строка содержит 1 букву "а", ее номер находится в [166, 495].
Если в строке нет буквы "а", его номер есть в [496, 1287].

А как насчет строки "aabgg"? Его число равно (45)+(8)+(7)+(6)+(5)+(4)+(1)=76

Коллизий нет, а расчет индекса O(sm(s+m)), что неплохо для m=5 и s=9.

EDIT: чтобы уточнить, давайте определим

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

Предположим, что строка из m букв, составленная из алфавита из s символов, содержит 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

person Beta    schedule 12.05.2020
comment
Я очень извиняюсь, я показал вопрос своему другу, и он сказал, что в английском так много ошибок, что лучше переписать, поэтому я воспользовался и написал проще - person NedLandy; 12.05.2020
comment
откуда взялось это (8)+(7)+(6)+(5)+(4)+(1) в примере? - person NedLandy; 12.05.2020
comment
Как Е(2,5,9) = 45? если E(2,5,9) = D(3,8)+D(4,8)+D(5,8) = C(10,7)+C(11,7)+C(12,7) ) = 120+330+792 = 1242 - person NedLandy; 12.05.2020
comment
@NedLandy: извините, я неправильно расшифровал алгебру. Я отредактирую. - person Beta; 13.05.2020

arrow_upward
0
arrow_downward

ну, я думаю, это выглядит как октябрь номер 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; 
   }
person Muhammed Salih    schedule 12.05.2020
comment
проблема в этом случае в том, что {0 0 0 0 1} = {0 0 0 1 0}, чего не произошло с номером окт - person NedLandy; 12.05.2020