部分排列

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

您需要排列，因此您应该在 substring 中的 i 之后捕获 之前和 之后的字符：

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

Answer 2

您可以使用标准库执行此操作：

// 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));
}

这依赖于 next_permutation 按字典顺序生成排列这一事实。因此，如果序列的尾部已排序，则反转尾部然后请求整个序列的下一个排列将头部移动到子集的下一个排列，并为下一次迭代再次对尾部进行排序。

如果不是很明显，将使用一对表示置换组合范围的迭代器调用仿函数。

Answer 3

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

但是如果您需要访问更多的东西，并且一次访问更多的东西，那么性能就真的开始变得很重要了。例如，一次访问 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

明显更快。

#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

这比 and 51 times faster than 快 30 倍！随着 n 和 r 的增长，这些性能数字的差异也越来越大。

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

部分排列

Partial permutations

c++

permutation