Какой самый быстрый способ конвертировать индекс комбинации в конкретную комбинацию? - PullRequest
Новая
       13

Какой самый быстрый способ конвертировать индекс комбинации в конкретную комбинацию?

0 голосов
/ 28 мая 2019

Я получаю индекс счетчика, который представляет конкретную комбинацию, когда вы перебираете все возможные комбинации определенного размера для списка возможных значений определенного размера.

Ниже показано, как я сейчас это делаю. 


int[] indexesOfTheCombination=getCombinationFromCombinationCountNumber(3,4,2);

public static int[] getCombinationFromCombinationCountNumber(int combinationNumberToGet,int NumberOfItemsInListOfPossibleValues,int combinationSize)
{
    int[] subset=new int[combinationSize];
    int[] set=new int[NumberOfItemsInListOfPossibleValues];
    int x=0;
    while(x < NumberOfItemsInListOfPossibleValues)
    {
    set[x]=x;
    x++;
    }

    int k = combinationSize;                       
    int ii=0;
    int[] s = new int[k];                  // indices 


    if (k <= NumberOfItemsInListOfPossibleValues) {
        // first index sequence: 0, 1, 2, ...
        for (int i = 0; (s[i] = i) < k - 1; i++);  
        subset=getSubset(set, s);  if(ii==combinationNumberToGet){return subset;} ii++;
        for(;;) {
            int i;
            // find position of item that can be incremented
            for (i = k - 1; i >= 0 && s[i] == NumberOfItemsInListOfPossibleValues - k + i; i--); 
            if (i < 0) {
                break;
            }
            s[i]++;                    // increment this item
            for (++i; i < k; i++) {    // fill up remaining items
                s[i] = s[i - 1] + 1; 
            }

            subset=getSubset(set, s); if(ii==combinationNumberToGet){return subset;} ii++;
        }
    }

    return subset;
} 


private static int[] getSubset(int[] input, int[] subset) {
    int[] result = new int[subset.length]; 
    for (int i = 0; i < subset.length; i++) 
        {result[i] = input[subset[i]];}
    return result;
}

Он выполняет итерацию возможных комбинаций, используя тот же метод, который использовался для создания индекса счетчика итераций, и затем возвращает массив индексов, который представляет индекс счета. Например, все возможные комбинации индексов из списка из 4 значений, комбинации из 2 будут, 

"count index"     "set of value indexes"
      0                  [0, 1]
      1                  [0, 2]
      2                  [0, 3]
      3                  [1, 2]
      4                  [1, 3]
      5                  [2, 3]

поэтому getCombinationFromCombinationCountNumber (3,4,2) выводит [1,2]. Эта функция, которую я сейчас использую, работает, но должна вычислять каждую комбинацию до тех пор, пока она не достигнет желаемой комбинации. Кажется, должен быть более эффективный способ сделать это. Если бы я был ограничен определенным списком возможных элементов с определенным размером комбинации, я мог бы использовать хэш-карту, но мне нужно что-то полностью обобщаемое. У кого-нибудь есть идеи, чтобы сделать это эффективным? Или итерация комбинаций, как это работает сейчас, уже лучший способ сделать это?

...