部分排列

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件事物的排列感兴趣,请立即停止阅读,因为访问次数太小而且无关紧要(除非您这样做十亿次).

但是如果你需要一次访问更多的东西,更多的东西,性能真的开始变得重要.例如,访问字符串26:"abcdefghijklmnopqrstuvwxyz",一次六个项目？随着排列,成本增长很快......

对于性能测试,最好将输出注释到终端,因为这往往是一个非常慢的操作,淹没了其他一切.

这个答案(目前接受的答案)如下所示:

#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速度要快得多.

#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%!很多这种速度增加可归因于缺少第一算法中隐含的分配和释放.

但是,我想指出一个更快的算法.

驱动程序看起来像:

#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

这是快30倍比使用应答std::next_permutation和快51倍比目前公认的答案!随着n并且r增长,这些性能数字的差异也会增长.

该链接库是免费的,开源的.实现位于链接处,可以从中复制/粘贴.我不会说它很简单.我只声称其性能引人注目.性能的差异是如此显着,以至于它可以在实际的时间内解决问题.

Answer 2

您需要排列，因此您应该捕获in之前和之后的字符：isubstring

substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());

完整计划coliru：

#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()
{
    comb("", "abcde", 3);
}

输出（重新格式化）：

abc abd abe acb acd ace adb adc ade aeb aec aed
bac bad bae bca bcd bce bda bdc bde bea bec bed
cab cad cae cba cbd cbe cda cdb cde cea ceb ced
dab dac dae dba dbc dbe dca dcb dce dea deb dec
eab eac ead eba ebc ebd eca ecb ecd eda edb edc