部分排列

我有以下递归函数用于输出部分组合：

void comb(string sofar, string rest, int n) {

    string substring;

    if (n == 0)
        cout << sofar << endl;
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

像这样调用：

comb("", "abcde", 3);

通过部分组合，我的意思是它使用 n 个选择和 r 个元素（而不是 n 个选择、n 个元素）。

但是，我想考虑元素的顺序（即排列）。我可以找到许多完整排列的算法，但不是部分排列。

现在是进行性能现实检查的时候了。如果您只对一次访问 5 件事 3 的排列感兴趣，请立即停止阅读，因为访问次数太少了，这并不重要（除非您可能已经这样做了十亿次）。

但如果您需要访问更多的东西，并且一次访问更多的东西，性能就真的开始变得重要了。例如，访问 26 个字符串：“abcdefghijklmnopqrstuvwxyz”，一次六个项目怎么样？随着排列，成本增长得非常快......

对于性能测试，最好注释掉终端的输出，因为这往往是一个非常慢的操作，会淹没其他所有内容。

这个答案 https://stackoverflow.com/a/34867494/576911（目前接受的）看起来像这样：

#include <chrono>
#include <iostream>
#include <string>

using std::string;
using std::cout;

void comb(string sofar, string rest, int n)
{
    // std::cout << "comb('" << sofar << "', '" << rest << "', " << n << ")\n";
    string substring;

    if (n == 0)
        ; //cout << sofar << '\n';
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

int main()
{
    std::string s("abcdefghijklmnopqrstuvwxyz");
    auto t0 = std::chrono::steady_clock::now();
    comb("",s, 6);
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>{t1-t0}.count() << '\n';
}

在我的系统上（clang++ -std=c++14 test.cpp -O3）输出：

14.2002

这个答案使用std::next_permutation https://stackoverflow.com/a/34868103/576911明显更快。

#include <algorithm>
#include <chrono>
#include <iostream>

// Requires: sequence from begin to end is sorted
//           middle is between begin and end
template<typename Bidi, typename Functor>
void for_each_permuted_combination(Bidi begin,
                                   Bidi middle,
                                   Bidi end,
                                   Functor func) {
  do {
    func(begin, middle);
    std::reverse(middle, end);
  } while (std::next_permutation(begin, end));
}

int
main()
{
    std::string s("abcdefghijklmnopqrstuvwxyz");
    auto t0 = std::chrono::steady_clock::now();
    for_each_permuted_combination(s.begin(), s.begin()+6, s.end(),
        [](auto first, auto last)
        {
//             for (; first != last; ++first)
//                 std::cout << *first;
//             std::cout << '\n';
        });
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>{t1-t0}.count() << '\n';
}

其输出：

8.39237

这快了 69%！这种速度的提高很大程度上可以归因于第一个算法中隐含的分配和释放的缺乏。

不过我想指出更快的算法 http://howardhinnant.github.io/combinations.html.

驱动程序看起来像：

#include "combinations"
#include <chrono>
#include <iostream>
#include <string>

int
main()
{
    std::string s("abcdefghijklmnopqrstuvwxyz");
    auto t0 = std::chrono::steady_clock::now();
    for_each_permutation(s.begin(), s.begin()+6, s.end(),
        [](auto first, auto last)
        {
//             for (; first != last; ++first)
//                 std::cout << *first;
//             std::cout << '\n';
            return false;
        });
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>{t1-t0}.count() << '\n';
}

输出是：

0.2742

This is 快 30 倍 than 答案使用std::next_permutation https://stackoverflow.com/a/34868103/576911 and 快 51 倍 than 目前接受的答案 https://stackoverflow.com/a/34867494/576911！并作为n and r随着增长，这些性能数字的差异也会增大。

The 链接库 http://howardhinnant.github.io/combinations.html是免费且开源的。实现位于链接处，可以从中复制/粘贴。我不会说这很简单。我只是声称它的性能令人信服。性能差异是如此巨大，以至于它可以决定问题能否在实际时间内得到解决。