c++ - 是否可以编写类似 next_permutation 的函数，但它只排列 r 值，而不是排列 n？

Question

std::next_permutation(和 std::prev_permutation)置换 [first, last) 范围内的所有值一共给出了n!排列(假设所有元素都是唯一的)。

是否可以这样写一个函数:

template<class Iter>
bool next_permutation(Iter first, Iter last, Iter choice_last);

排列 [first, last) 范围内的元素但只选择 [first, choice_last) 范围内的元素.即我们可能有 20 个元素，并希望遍历其中 10 个选择的所有排列，20 P 10 选项与 20 P 20。

• Iter 对我来说是一个随机访问迭代器，但如果它可以实现为双向迭代器，那就太好了!
• 需要的外部存储器越少越好，但对我来说这无关紧要。
• 每次迭代中选择的元素被输入到序列的第一个元素。

这样的功能可以实现吗？有人知道任何现有的实现吗？

这基本上是我正在做的事情来解决这个问题。也欢迎就如何改进这一点提出建议。

• 从 vector 开始V的 N我想访问 R 的每个排列的元素从中选择的元素 ( R <= N )。
• 构建 vector I长度R具有值 { 0, 1, 2, ... R - 1 }作为 V 元素的索引
• 在每次迭代中，构建一个 vector C长度R具有值 { V[I[0]], V[I[1]], ... V[I[R - 1]] }
• 对 C 中的值做一些事情.
• 应用一个函数来置换 I 的元素如果可以，再次迭代。

该函数如下所示:

bool NextPermutationIndices(std::vector<int> &I, int N)
{
    const int R = I.size();
    for (int i = R - 1; ; --i) {
        if (I[i] < N - R + i) {
            ++I[i];
            return true;
        }

        if (i == 0)
            return false;

        if (I[i] > I[i-1] + 1) {
            ++I[i-1];
            for (int j = i; j < R; ++j)
                I[j] = I[j-1] + 1;
            return true;
        }
    }
}

由于所有可能的差一错误，该函数非常复杂，而且使用它的所有东西都比可能需要的更复杂。

---

编辑:

事实证明，这比我想象的要明显容易。来自 here ，我能够找到许多我需要的精确算法(组合、排列等)的精确实现。

template<class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first,
                              BidirectionalIterator middle,
                              BidirectionalIterator last)
{
    std::reverse(middle, last);
    return std::next_permutation(first, last);
}

此外，还有一种以类似方式工作的组合算法。不过，其实现要复杂得多。

Answer 1

为了遍历 nPk 排列，我使用了 this old CUJ article 中介绍的 for_each_permutation() 算法。前。它使用了 Knuth 的一个很好的算法，该算法在原位旋转元素，最后将它们保留在原始顺序中。因此，它满足您无外部存储器的要求。它也适用于双向迭代器。它不符合您看起来像 next_permutation() 的要求。但是，我认为这是一个胜利——我不喜欢有状态的 API。