c++ - 查找组合数量的算法

Question

假设我有四个数字0,1,1,3。我想找到两个数字的唯一组合的数量。请帮我写这个算法和代码。我知道这更像是一个数学问题，但我仍然必须编写代码。请帮我。

Answer 1

从您的示例集中0,1,1,3，我假设您希望在输入中允许重复，这使得查找唯一组合的数量变得更加困难。

由于您只想选择唯一的对，这比选择唯一的 n 组要简单得多（至少在允许重复时）。

这个想法是首先删除所有重复项，同时记录有多少输入具有重复值。

你的答案将是

n C 2 + m其中n是不同元素m的#，是重复元素的#。

，0,1,1,3所以你n = 3得到m = 13 C 2 + 1 = 3 + 1 = 4

(0, 1), (0, 3), (1, 1), (1, 3)

下面的代码给出了一个假设你的输入是一个整数向量的实现。但是您可以将 int 更改为已<定义的任何类型。

unsigned long long unique_pairs(const std::vector<int>& elements){
    std::map<int, int> counts;
    for (int i = 0; i < elements.size(); ++i){
        ++counts[elements[i]];
    }
    unsigned long long n = counts.size(); // # of different elements
    unsigned long long m(0);              // # of repeated elements
    for (std::map<int, int>::iterator it = counts.begin(); it != counts.end(); ++it){
        if (it->second != 1){
          ++m;
        }
    }
    return n * (n - 1) / 2 + m; // n C 2 + m
}

演示

Answer 2

对你来说一个简单的伪代码是做这样的事情：

1- getInputs(std::vector<int> inputs)//负责读取用户的输入

2- removeDuplicates(std:vector<int> inputs)//从输入中删除重复项

3- calculateCombination(n = length(inputs))//如果您正在寻找组合，您应该实施n!/((n-2)!*2!)，或者如果您正在寻找排列，您应该实施n!/(n-2)!

Answer 3

您必须在其中使用组合公式。你应该为它写一个阶乘函数。

假设例如您有 4 个数字，并且您想要不重复的组合数量，因此使用4C2

这里 2 是要组合使用的元素数量

4 是您拥有的元素总数

所以你可以用4! /(2!*(4-2)!) ....所以这个计算会给你组合的总数而不重复

注意：对于独特的组合，您应该有独特的元素