Подсчет Комбинаций

Вообще говоря, определение числа комбинаций конкретного множества довольно тривиально. Однако распространение этого на мультинабор, где каждый элемент повторяется определенное количество раз, значительно сложнее и не так хорошо документировано. @WorldSEnder связан с ответом math/stackexchange, который имеет комментарий со ссылкой на эту замечательную статью в combinatorics под названием Combinatorial Generation Фрэнка Раски. Если вы переходите на страницу 71, там есть раздел, который рассматривает эту тему с большей строгостью.

Основные определения

1. множество - совокупностьразличных объектов. - Например, {a, b} то же самое, что {a, a, b}, и оба имеют мощность 2
2. Multiset-аналогично набору, но допускает дублирование записей. - Например, {a, b} и {a, a, b} являются различными мультинаборами с мощностью 2 и 3 соответственно
3. биномиальный коэффициент-дает число k - элемент подмножества множестваn -элементов.
4. Мультимножество коэффициент/число - число мультимножеств мощности к с элементов, взятых из конечного набора.

Заблуждения

Существует мнение, что существует простая формула, которая быстро вычислит количество комбинаций для мультинабора длины k, где каждый элемент повторяется определенное количество раз (см. комментарии с высоким процентом цитирования выше). Ниже мы рассмотрим каждый из хорошо известные методы. Начнем с общего применения биномиального коэффициента. Мы сразу же видим, что это не удастся, так как он строго предназначен для вычисления числа комбинаций множества , где повторяющиеся записи не допускаются. В нашем случае допускаются дубликаты. Ниже на странице Википедии есть раздел под названиемколичество комбинаций с повторением . Это выглядит многообещающе, поскольку у нас есть некоторые копирование. Мы также видим модифицированный биномиальный коэффициент, который кажется еще более перспективным. Более пристальный взгляд показывает, что это тоже не удастся, поскольку это строго относится к мультинаборам, где каждый элемент повторяется до k раз.

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

" во-первых, рассмотрим обозначения для мультинаборов, которые будут представлять {a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d} (6 as, 2 bs, 3 cs, 7 ds) в таком виде: "

Это выглядит как хороший кандидат для того, что мы пытаемся вывести. Тем не менее, вы увидите, что они продолжают выводить число способов, которыми вы можете построить мультинабор мощности 18 из набора 4 различных элементов. Это эквивалентно числуцелых композиций 18 длины 4. Например

18 + 0 + 0 + 0
17 + 1 + 0 + 0
16 + 2 + 0 + 0
       .
       .
       .
5 +  4 + 6 + 3
4 +  5 + 6 + 3
3 +  6 + 6 + 3
       .
       .
       .
0 +  1 + 0 + 17
0 +  0 + 1 + 17
0 +  0 + 0 + 18

Как вы можете видеть, порядок имеет значение с композициями, которые явно не относятся к нашему ситуация.

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

Работающий Алгоритм

unsigned long int getCombinationCount(std::vector<double> nums) {

    unsigned long int n = nums.size();
    unsigned long int n2 = n / 2;
    unsigned long int numUnique = 1;
    unsigned long int numCombinations;

    std::sort(nums.begin(), nums.end());
    std::vector<int> numReps;

    double testVal = nums[0];
    numReps.push_back(1);

    for (std::size_t i = 1; i < n; ++i) {
        if (nums[i] != testVal) {
            numReps.push_back(1);
            testVal = nums[i];
            ++numUnique;
        } else {
            ++numReps[numUnique - 1];
        }
    }

    int myMax, r = n2 + 1;
    std::vector<double> triangleVec(r);
    std::vector<double> temp(r);
    double tempSum;

    myMax = r;
    if (myMax > numReps[0] + 1)
        myMax = numReps[0] + 1;

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

    temp = triangleVec;

    for (std::size_t k = 1; k < numUnique; ++k) {
        for (int i = n2; i > 0; --i) {
            myMax = i - numReps[k];
            if (myMax < 0)
                myMax = 0;

            tempSum = 0;
            for (int j = myMax; j <= i; ++j)
                tempSum += triangleVec[j];

            temp[i] = tempSum;
        }
        triangleVec = temp;
    }

    numCombinations = (unsigned long int) triangleVec[n2];

    return numCombinations;
}

Объяснение с использованием модифицированного треугольника Паскаля

Записи в традиционном треугольнике Паскаля (PT отсюда и далее) представляют собой биномиальный коэффициент, где строка треугольника является числом элементов в вашем наборе и столбец-это длина комбинаций, которые вы хотите создать. Построение треугольника-это ключ к тому, как мы будем решать поставленную задачу.

Если вы заметите, что для традиционного PT, чтобы получить конкретную запись, скажем (i, j), где i - строка и j - столбец, вы должны добавить записи (i - 1, j-1) и (i-1, j). Вот вам иллюстрация.

                  1
                1   1
              1   2   1            N.B. The first 10 is in the 5th row and 3rd column
            1   3   3   1               and is obtained by adding the entries from the
          1   4   6   4   1             4th row and 2nd/3rd.
        1   5   10  10  5   1
      1   6   15  20  15  6   1

Мы можем распространить это на a общий мультисет, где каждый элемент повторяется определенное количество раз. Давайте рассмотрим несколько примеров.

Пример 1: v1 = {1, 2, 2}, v2 = {1, 2, 2, 3, 3, 3}, и v3 = {1,2,2,3,3,3,4,4,4,4}

Ниже мы имеем все возможные комбинации v1 choose 1 - 3, а также v2 choose 1 - 6.

     [,1]                    [,1]
[1,]    1               [1,]    1
[2,]    2               [2,]    2
                        [3,]    3

     [,1] [,2]               [,1] [,2]
[1,]    1    2          [1,]    1    2
[2,]    2    2          [2,]    1    3
                        [3,]    2    2
                        [4,]    2    3
                        [5,]    3    3

     [,1] [,2] [,3]          [,1] [,2] [,3]
[1,]    1    2    2     [1,]    1    2    2
                        [2,]    1    2    3
                        [3,]    1    3    3
                        [4,]    2    2    3
                        [5,]    2    3    3
                        [6,]    3    3    3

                             [,1] [,2] [,3] [,4]
                        [1,]    1    2    2    3
                        [2,]    1    2    3    3
                        [3,]    1    3    3    3
                        [4,]    2    2    3    3
                        [5,]    2    3    3    3

                             [,1] [,2] [,3] [,4] [,5]
                        [1,]    1    2    2    3    3
                        [2,]    1    2    3    3    3
                        [3,]    2    2    3    3    3

                             [,1] [,2] [,3] [,4] [,5] [,6]
                        [1,]    1    2    2    3    3    3

Запишем число комбинаций для всех k как для v1, так и для v2.

2  2  1
3  5  6  5  3  1

Я собираюсь дать вам число комбинаций для всех k из v3 (я оставлю это для читатель их перечислит).

4  9 15 20 22 20 15  9  4  1

Мы комбинируем результаты выше особым образом и отмечаем, что вещи начинают выглядеть очень знакомыми.

         2  2  1
     3   5   6   5  3  1
4  9  15  20  22  20  15  9  4  1

Мы добавляем несколько из них в качестве держателей мест, чтобы завершить этот модифицированный PT

                1   1
            1   2   2   1
      1   3   5   6   5   3   1
1  4  9  15  20  22  20  15   9  4  1

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

Мы позволяем частоте каждого элемента направлять нас.

Для например, чтобы получить третью строку, представляющую число комбинаций v2 choose 1 - 6 (игнорируя первую 1), мы смотрим на строку 2. Поскольку частота 3-го элемента равна 3, мы добавляем 4 элемента (3 + 1.. так же, как и с биномиальными коэффициентами для нахождения числа комбинаций множеств с различными элементами, мы добавляем 2 записи вместе или 1 + 1) в строку выше со столбцом, меньшим или равным столбцу, который мы находим. Итак, мы имеем:

if the column index is non-positive or greater than the 
number of columns in the previous row, the value is 0

    v2 choose 3
(3, 2) =  (2, 2 - 3) + (2, 2 - 2) + (2, 2 - 1) + (2, 2 - 0)
       =       0     +      0     +      1     +    2 
       =   3

v2 choose 4           
(3, 3) =  (2, 3 - 3) + (2, 3 - 2) + (2, 3 - 1) + (2, 3 - 0)
       =       0     +      1     +      2     +    2 
       =   5           

v2 choose 5 
(3, 4) =  (2, 4 - 3) + (2, 4 - 2) + (2, 4 - 1) + (2, 4 - 0)
       =       1     +      2     +      2     +    1 
       =   6

v2 choose 6                                   outside of range
(3, 5) =  (2, 5 - 3) + (2, 5 - 2) + (2, 5 - 1) + (2, 5 - 0)
       =       2     +      2     +      1     +    0 
       =   5

       etc.

Продолжая эту логику, давайте посмотрим, если мы можем получить число k -комбинаций для v3. Поскольку частота 4-го элемента равна 4, нам нужно будет добавить 5 записей вместе.

v3 choose 3
(4, 2) =  (3, 2 - 4) + (3, 2 - 3) + (3, 2 - 2) + (3, 2 - 1) + (3, 2 - 0)
       =       0     +      0     +     0      +      1     +     3 
       =   4

v3 choose 4 
(4, 3) =  (3, 3 - 4) + (3, 3 - 3) + (3, 3 - 2) + (3, 3 - 1) + (3, 3 - 0)
       =       0     +      0     +      1     +    3       +     5
       =   9           

v3 choose 5  
(4, 4) =  (3, 4 - 4) + (3, 4 - 3) + (3, 4 - 2) + (3, 4 - 1) + (3, 4 - 0)
       =       0     +     1      +      3     +     5      +     6
       =   15

v3 choose 6
(4, 5) =  (3, 5 - 4) + (3, 5 - 3) + (3, 5 - 2) + (3, 5 - 1) + (3, 5 - 0)
       =       1     +     3      +      5     +       6    +    5
       =   20

       etc.

И действительно, мы получаем правильное число k-комбинаций v3.

Пример 2: z1 = {1,1,1,2}, z2 = {1,1,1,1,2,3,3,3,3,3}, и z3 = {1,1,1,1,2,3,3,3,3,3,4,4}

Вы заметите, что мы строим эти векторы так, что каждый последующий вектор содержит предыдущие векторы. Мы делаем это для того, чтобы иметь возможность правильно построить наше модифицированный ПТ. Это аналогично традиционному PT, Где с каждой последующей строкой мы просто добавляем одно число к предыдущей строке. Модифицированный PT для этих векторов:

                1   1   1  1
             1   2   2   2   1
      1  3  5  7   8   8   7   5   3  1
  1  4   9  15  20  23   23  20  15  9  4  1

Построим z2 choose 6 и z3 choose 9, чтобы убедиться, что мы правы:

 z2 choose 6
      [,1] [,2] [,3] [,4] [,5] [,6]
 [1,]    1    1    1    2    3    3
 [2,]    1    1    1    3    3    3      This shows that we produce 7 combs
 [3,]    1    1    2    3    3    3      just as predicted by our modified
 [4,]    1    1    3    3    3    3      PT (i.e. entry (3, 6 + 1) = 7)
 [5,]    1    2    3    3    3    3
 [6,]    1    3    3    3    3    3
 [7,]    2    3    3    3    3    3


 z3 choose 9
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,]    1    1    1    2    3    3    3    3    3
[2,]    1    1    1    2    3    3    3    3    4
[3,]    1    1    1    2    3    3    3    4    4  This shows that we produce 9 
[4,]    1    1    1    3    3    3    3    3    4  combs just as predicted by 
[5,]    1    1    1    3    3    3    3    4    4  our modified PT (i.e. entry
[6,]    1    1    2    3    3    3    3    3    4  (4, 9 + 1) = 9)
[7,]    1    1    2    3    3    3    3    4    4
[8,]    1    1    3    3    3    3    3    4    4
[9,]    1    2    3    3    3    3    3    4    4

Так же, как и краткое Примечание, первый ряд удерживающих место единиц аналогичен второму ряду традиционного PT (т. е. 1 1). Грубо говоря (см. код для крайних случаев), если первый элемент имеет частоту m , первый ряд модифицированного PT будет содержать m + 1 единиц.

Причина, по которой нет общей формулы (например, что-то похожее на биномиальный коэффициент)

Как вы можете видеть из приведенных выше 2 примеров, модифицированные PT основаны на конкретных мультинаборах и, следовательно, не могут быть обобщены. Даже если вы рассматриваете мультинаборы определенной мощности, состоящие из одних и тех же различных элементов, модифицированные PT будут отличаться. Например, мультисет a = {1, 2, 2, 3, 3, 3} и b = {1, 1, 2, 2, 3, 3} генерируют следующие модифицированные PT соответственно:

     1 1
   1 2 2 1
1 3 5 6 5 3 1

    1 1 1
  1 2 3 2 1
1 3 6 7 6 3 1

Обратите внимание, что a choose 2 = 5 тогда как b choose 2 = 6.

Контрольные показатели:

Вот ссылка на ideone, демонстрирующая ускорение нового алгоритма. Для вектора {4, 2, 6, 4, 9, 8, 2, 4, 1, 1, 6, 9} время для оригинала было 2285718 тактовыми тиками, тогда как алгоритм выше завершен в 8 тактовыми тиками для общего ускорения 2285728 / 8 = 285714.75... более чем в сто тысяч раз быстрее. Они оба возвращают одинаковое количество комбинаций, как ну (то есть 122). Большая часть прироста скорости происходит за счет отказа от явного генерирования любых комбинаций (или перестановок, как это делает код OP).