c++ - 集合与重复的组合

Question

http://stackoverflow.com上有很多链接如何组合:Generating combinations in c++但是这些链接假设是从一个无限的集合中提取而不重复的。当给定一个确实有重复的有限集合时，这些算法会构造重复项。例如，您可以看到链接问题的可接受解决方案在我此处构建的测试用例上失败:http://ideone.com/M7CyFc

给定输入集:vector<int> row {40, 40, 40, 50, 50, 60, 100};

我希望看到:

• 40 40 40
• 40 40 50
• 40 40 60
• 40 40 100
• 40 50 50
• 40 50 60
• 40 50 100
• 40 60 100
• 50 50 60
• 50 50 100
• 50 60 100

显然，我可以使用旧方法存储输出并在生成时检查重复项，但这需要大量额外的内存和处理能力。 C++ 是否为我提供了替代方案？

Answer 1

根据定义，组合不遵守顺序。这使我们可以自由地按照我们认为合适的顺序排列数字。最值得注意的是，我们可以依赖于提供组合排名。当然，对组合进行排序的最合乎逻辑的方式是按排序顺序排列，因此我们将取决于我们输入的排序。

标准库中已经有这方面的先例。例如 lower_bound 我们将在这个解决方案中实际使用它。然而，当普遍使用时，这可能需要用户在通过之前进行排序。

我们将为此编写的函数将接收指向下一个组合的排序集合的迭代器，以及指向当前组合的迭代器。我们还需要大小，但这可以从组合的迭代器之间的距离得出。

template <typename InputIt, typename OutputIt>
bool next_combination(InputIt inFirst, InputIt inLast, OutputIt outFirst, OutputIt outLast) {
    assert(distance(inFirst, inLast) >= distance(outFirst, outLast));

    const auto front = make_reverse_iterator(outFirst);
    const auto back = make_reverse_iterator(outLast);
    auto it = mismatch(back, front, make_reverse_iterator(inLast)).first;

    const auto result = it != front;

    if (result) {
        auto ub = upper_bound(inFirst, inLast, *it);

        copy(ub, next(ub, distance(back, it) + 1), next(it).base());
    }
    return result;
}

这个函数是以其他算法函数的格式编写的，因此任何支持双向迭代器的容器都可以与它一起使用。对于我们的示例，尽管我们将使用:const vector<unsigned int> row{ 40U, 40U, 40U, 50U, 50U, 60U, 100U };这必然是排序的:

vector<unsigned int> it{ row.cbegin(), next(row.cbegin(), 3) };

do {
    copy(it.cbegin(), it.cend(), ostream_iterator<unsigned int>(cout, " "));
    cout << endl;
} while(next_combination(row.cbegin(), row.cend(), it.begin(), it.end()));

Live Example

---

写完这个答案后，我做了更多的研究并找到了 N2639它提出了一个标准化的next_combination ，这是:

• Actively under consideration for a future TR, when work on TR2 was deferred pending
• Viewed positively at the time
• Due at least one more revision before any adoption
• Needed some reworking to reflect the addition of C++11 language facilities

[ Source ]

使用 N2639 的引用实现需要可变性，因此我们将使用:vector<unsigned int> row{ 40U, 40U, 40U, 50U, 50U, 60U, 100U }; .我们的示例代码变为:

vector<unsigned int>::iterator it = next(row.begin(), 3);

do {
    copy(row.begin(), it, ostream_iterator<unsigned int>(cout, " "));
    cout << endl;
} while(next_combination(row.begin(), it, row.end()));

Live Example