c++ - 重复组合计数

我有一种非常低效的方法来计算 N/2 的组合大小为 N 的数组中的项目。我所做的是对数组进行排序，然后遍历数组的排列，创建包含一半元素的多重集并将其插入到一个集合中。最后我得到了集合的计数。

long GetCombinations(std::vector<double> nums) {
    long combinations = 0;
    std::sort(nums.begin(), nums.end());
    std::set<std::multiset<double>> super_set;

    do {
        std::multiset<double> multi_set;

        for (unsigned int i = 0; i < nums.size() / 2; ++i)
            multi_set.insert(nums[i]);

        auto el = (super_set.insert(multi_set));

        if (el.second)
            ++combinations;

    } while (std::next_permutation(nums.begin(), nums.end()));

    return combinations;
}

该代码有效，但效率非常低。对于给定的数组 [0.5, 0.5, 1, 1]尺寸 2 有 3 种组合:

0.5, 0.5
1, 1
1, 0.5

是否有不同的算法或方法可以提高此代码的速度？

最佳答案

计数组合

一般来说，确定特定集合的组合数是非常简单的。但是，将其扩展到每个元素重复特定次数的多重集要困难得多，并且没有很好的记录。 @WorldSEnder 链接到具有 comment 的数学/stackexchange 答案链接到这篇精彩的组合数学文章，名为 Combinatorial Generation通过弗兰克·拉斯基。如果您转到第 71 页，则有一个部分更严格地处理此主题。

基本定义

套装 - 合集独特对象。
- 例如{a, b}与 {a, a, b} 相同并且都具有基数 2

Multiset - 类似于集合，但允许重复条目。
- 例如{a, b}和 {a, a, b}是基数分别为 2 和 3 的不同多重集

二项式系数 - 给出 n 元素集的 k 元素子集的数量。

Multiset Coefficient/Number - 基数为 k 且元素取自有限集的多重集的数量。

误解

人们相信有一个简单的公式可以快速计算长度为 k 的多组的组合数，其中每个元素重复特定次数(请参阅上面高度赞成的评论)。下面，我们检查每种众所周知的方法。

让我们从二项式系数的一般应用开始。我们立即看到这将失败，因为它严格意味着计算 的组合数。集 ，其中不允许重复条目。在我们的例子中，允许重复。

在维基百科页面上进一步阅读，有一个名为 Number of combinations with repetition 的部分。 .这看起来很有希望，因为我们确实有一些复制。我们还看到了修改后的二项式系数，这似乎更有希望。仔细观察会发现这也会失败，因为这严格适用于每个元素最多重复 k 次的多重集。

最后，我们尝试使用 multiset coefficient .列出的示例之一看起来与我们试图完成的非常相似。

“首先，考虑表示 {a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d} (6如, 2 bs, 3 cs, 7 ds) 以这种形式:"

这看起来是我们试图推导出的一个很好的候选者。但是，您将看到它们继续推导出可以从 4 个不同元素的集合构造基数为 18 的多重集的方法数。这相当于integer compositions的数量长度为 4 的 18 个。

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

正如您所看到的，顺序与构图很重要，这显然不适用于我们的情况。

提到的最后两种方法源自著名的 Stars and Bars简单计数问题的方法。据我所知，这种方法不能轻易扩展到我们的情况。

一种工作算法

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

使用修正的帕斯卡三角形进行解释

繁体中的条目Pascal's Triangle (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

我们可以将其扩展到一个通用的多重集，其中每个元素重复特定的次数。让我们考虑几个例子。

示例 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

我要给你v3的所有k的组合数(我将留给读者列举它们)。

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

这是什么意思？有点清楚的是，每个连续行中的数字都是前一行中数字的组合。但是怎么办？...

We let the frequency of each element guide us.

例如，要获取代表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.

继续这个逻辑，让我们看看我们是否可以获得v3的k组合数.由于第 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.

事实上，我们确实得到了 v3 的正确 k 组合数。 .

示例 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}
您会注意到我们正在构建这些 vector ，使得每个连续的 vector 都包含前一个 vector 。我们这样做是为了能够正确构建我们修改后的 PT。这类似于传统的 PT，对于每一行，我们只是在前一行添加一个数字。这些 vector 的修改后的 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 的链接展示了新算法的加速。对于 vector {4, 2, 6, 4, 9, 8, 2, 4, 1, 1, 6, 9} ，原来的时间是2285718时钟滴答，而上述算法在 8 中完成时钟滴答，总加速2285728 / 8 = 285714.75 ... 快十万倍。它们都返回相同数量的组合(即 122)。大多数速度提升来自避免显式生成任何组合(或 OP 代码所做的排列)。

关于c++ - 重复组合计数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50949159/

c++ - 重复组合计数

上一篇：polymer - 焦点和模糊事件的事件重定向

下一篇：java - 在 Java 中导入新框架？