Существует ли функция для генерации определенной комбинации n Multichoose r с учетом номера индекса? - PullRequest
Новая
       7

Существует ли функция для генерации определенной комбинации n Multichoose r с учетом номера индекса?

0 голосов
/ 03 мая 2018

Например, 3 multihoose 2 имеет следующие комбинации: 

i   combo
0 = [0,0]
1 = [0,1]
2 = [0,2]
3 = [1,1]
4 = [1,2]
5 = [2,2]

Может ли быть написана функция с аргументами n, r, i, которая возвращает указанную комбинацию, без перебора каждой комбинации перед ней?

1 Ответ

0 голосов
/ 04 мая 2018

Может ли быть написана функция с аргументами n, r, i, которая возвращает указанную комбинацию, без перебора каждой комбинации перед ней?

Да. Мы должны немного подсчитать, чтобы решить эту проблему. Чтобы лучше проиллюстрировать, как это можно разбить на очень простые мелкие задачи, мы рассмотрим более крупный пример. Рассмотрим все комбинации из 5 выбранных 3 одновременно без повторов (далее мы будем говорить, что 5 выбирают 3). 

      [,1] [,2] [,3]
 [1,]    1    2    3
 [2,]    1    2    4
 [3,]    1    2    5
 [4,]    1    3    4
 [5,]    1    3    5
 [6,]    1    4    5
 [7,]    2    3    4
 [8,]    2    3    5
 [9,]    2    4    5
[10,]    3    4    5

Обратите внимание на первые 6 строк. Если мы удалим первый столбец из этих 6 строк и вычтем 1 из каждого элемента, мы получим: 

      [,1] [,2]                   [,1] [,2]
[1,]    2    3              [1,]    1    2
[2,]    2    4  subtract 1  [2,]    1    3
[3,]    2    5    --->>>>   [3,]    1    4
[4,]    3    4              [4,]    2    3
[5,]    3    5              [5,]    2    4
[6,]    4    5              [6,]    3    4

Матрица справа - это точно все комбинации из 4 вариантов выбора 2. Продолжая, мы видим, что «вторая» группа (то есть строки с 7 по 9 исходной матрицы) также выглядит в следующем порядке: 

     [,1] [,2]                    [,1] [,2]
[1,]    3    4              [1,]    1    2
[2,]    3    5  subtract 2  [2,]    1    3
[3,]    4    5    --->>>>   [3,]    2    3

Это просто 3 выбора 2. Мы начинаем видеть, как разворачивается паттерн. А именно, что все комбинации меньших n и r содержатся в наших родительских комбинациях. Эта схема продолжается, пока мы движемся вправо. Осталось только следить за тем, какая комбинация нам нужна.

Ниже приведен вышеупомянутый алгоритм, записанный в C++ (примечание: нет никакой проверки данных): 

template <typename T>
double nChooseK(T n, T k) {
    // Returns number of k-combinations from n elements.
    // Mathematically speaking, we have: n!/(k!*(n-k)!)
    if (k == n || k == 0)
        return 1;
    else if (k > n || n < 0)
        return 0;

    double nCk;
    double temp = 1;
    for (int i = 1; i <= k; i++)
        temp *= (double) (n - k + i) / i;

    nCk = std::round(temp);
    return nCk;
}

std::vector<int> nthCombination(int n, int r, double i) {

    int j = 0, n1 = n - 1, r1 = r - 1;
    double temp, index1 = i, index2 = i;
    std::vector<int> res(r);

    for (int k = 0; k < r; k++) {
        temp = nChooseK(n1, r1);
        while (temp <= index1) {
            index2 -= nChooseK(n1, r1);
            n1--;
            j++;
            temp += nChooseK(n1, r1);
        }
        res[k] = j;
        n1--;
        r1--;
        j++;
        index1 = index2;
    }

    return res;
}

Вызывая это в нашем примере выше с 5 выберите 3, мы получим: 

nthCombination(5, 3, 0) -->> 0 1 2
nthCombination(5, 3, 1) -->> 0 1 3
nthCombination(5, 3, 2) -->> 0 1 4
nthCombination(5, 3, 3) -->> 0 2 3
nthCombination(5, 3, 4) -->> 0 2 4
nthCombination(5, 3, 5) -->> 0 3 4
nthCombination(5, 3, 6) -->> 1 2 3
nthCombination(5, 3, 7) -->> 1 2 4
nthCombination(5, 3, 8) -->> 1 3 4
nthCombination(5, 3, 9) -->> 2 3 4

Этот подход также очень эффективен. Ниже мы получаем миллиардную комбинацию из 40 вариантов выбора 20 (которая генерирует более 100 миллиардов комбинаций) мгновенно: 

      // N.B. base zero so we need to subtract 1
nthCombination(40, 20, 1000000000 - 1)  -->>
   0  1  2  3  4  5  8  9 14 16 18 20 22 23 31 33 34 35 38 39

Редактировать

Как указывает ОП в комментариях, они привели пример с повторениями. Решение очень похоже, и оно сводится к подсчету. Сначала нам нужна функция подсчета, похожая на nChooseK, но она учитывает повторы. Функция ниже делает именно это: 

double combsWithReps(int n, int r) {
    // For combinations where repetition is allowed, this
    // function returns the number of combinations for
    // a given n and r. The resulting vector, "triangleVec"
    // resembles triangle numbers. In fact, this vector
    // is obtained in a very similar method as generating
    // triangle numbers, albeit in a repeating fashion.

    if (r == 0)
        return 1;

    int i, k;
    std::vector<double> triangleVec(n);
    std::vector<double> temp(n);

    for (i = 0; i < n; i++)
        triangleVec[i] = i+1;

    for (i = 1; i < r; i++) {
        for (k = 1; k <= n; k++)
            temp[k-1] = std::accumulate(triangleVec.begin(), triangleVec.begin() + k, 0.0);

        triangleVec = temp;
    }

    return triangleVec[n-1];
}

А вот функция, которая генерирует комбинацию ith с повторениями. 

std::vector<int> nthCombWithRep(int n, int r, double i) {

    int j = 0, n1 = n, r1 = r - 1;
    double temp, index1 = i, index2 = i;
    std::vector<int> res(r);

    for (int k = 0; k < r; k++) {
        temp = combsWithReps(n1, r1);
        while (temp <= index1) {
            index2 -= combsWithReps(n1, r1);
            n1--;
            j++;
            temp += combsWithReps(n1, r1);
        }
        res[k] = j;
        r1--;
        index1 = index2;
    }

    return res;
}

Это очень похоже на первую функцию выше. Вы заметите, что n1-- и j++ удалены из конца функции, а также что n1 инициализируется в n вместо n - 1.

Вот приведенный выше пример: 

nthCombWithRep(40, 20, 1000000000 - 1)  -->>
    0  0  0  0  0  0  0  0  0  0  0  4  5  6  8  9 12 18 18 31
...