置换算法的迭代版本

Question

为了学习，我编写了一个递归算法的迭代版本，用于为给定的一组唯一整数生成一组排列。

我能做些改进来提高可读性和性能吗？

我还在各种来源中看到，当将递归算法转换为迭代算法时，通常使用堆栈数据结构来“替换”递归情况下使用的调用堆栈。这里我没有使用std::stack，但是我可以使用它来简化我的实现吗？

using std::vector;

vector<vector<int>> permutations(vector<int> integers) {
    vector<vector<int>> curr_perms;

    if (integers.size() <= 1) {
        curr_perms.push_back(integers);
        return curr_perms;
    }

    size_t sz = integers.size();

    vector<vector<int>> next_perms;

    // initialise with the one permutation of the last single element
    vector<int> t = { integers[sz - 1] };
    curr_perms.emplace_back(t);

    // backwards iterating a sequence of at least two elements
    for (int i = sz - 2; i >= 0; --i) {
        auto first = integers[i];

        for (const auto &s : curr_perms) {
            for (auto j = 0U; j < s.size() + 1; ++j) {
                vector<int> p(s.begin(), s.end());  // make a copy 
                p.insert(p.begin() + j, first);     // shuffle in 'first' element
                next_perms.push_back(std::move(p)); // and add this as a new permutation
            }
        }

        // permutations found in this iteration are the input for the next
        std::swap(next_perms, curr_perms); // <-- is this needlessly copying all the elements?
        next_perms.clear();
    }

    return curr_perms;
}

Answer 1

递归算法通常是可读的和漂亮的，但效率不高:堆栈消耗可能很大，内存分配非常充足，而且您不得不同时计算整组排列。

当您机械地将递归算法转换成它的迭代形式时，您通常会失去它的大部分美感和可读性，而不会在性能方面获得太多好处:您只是用一个数据结构来模拟编译器应该做的事情。有时它可能很有用，但您通常可以假设编译器会比您自己做得更好。

因此，我建议研究两种备选办法：

• 第一种方法是以标准库的方式实现它，并提供一个std::next_permutation函数，该函数以字典顺序返回下一个排列(例如，请参见我对这个问题的回答)。但是，使用SJT算法可以改进它，这将是一种选择的练习；
• 第二种方法是保持递归算法的一般增量推理，但使用迭代形式获得的附加知识:实际上，与递归形式相反，您可以预先知道最终返回多少排列，从而可以避免所有的分配。

例如：

#include <vector>

std::vector<std::vector<int>> permutations_set(const std::vector<int>& set) {

    if (set.empty()) return {};

    auto current = std::begin(set);

    // the unique memory allocation
    std::vector<std::vector<int>> permutations(factorial(set.size()), {*current});

    for (++current; current != std::end(set); ++current) {
        std::size_t offset = 0; // offset plays the central role here; you could say it replaces the stack
        for (auto& permutation : permutations) {
            const auto initial_size = permutation.size();
            permutation.insert(std::next(std::begin(permutation), offset), *current); 
            if (offset++ == initial_size) offset = 0;
        }
    }

    return permutations;           
}