c++ - 部分排列

Question

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

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 个元素)。

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

Answer 1

是时候进行性能现实检查了。如果您只对一次访问 5 件事 3 的排列感兴趣，请立即停止阅读，因为访问次数太少以至于无关紧要(除非您可能正在这样做十亿次)。

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

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

This answer (目前接受的)看起来像这样:

#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

This answer using std::next_permutation明显更快。

#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%!这种速度的提高在很大程度上可以归因于第一种算法中隐含的分配和释放的缺乏。

但是我想向您指出an even faster algorithm .

驱动看起来像:

#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

这比 the answer using std::next_permutation 快 30 倍并且比 the currently accepted answer 快 51 倍 !随着 n 和 r 的增长，这些性能数字的差异也越来越大。

linked library是免费和开源的。实现在链接上，可以从中复制/粘贴。我不会说它很简单。我只声称它的性能令人信服。性能上的差异是如此巨大，以至于它可以决定是否在实际时间内解决问题。