是否有可能编写一个类似next_permutation的函数,但只排列r值,而不是n?

std::next_permutation(和std::prev_permutations)对范围内的所有值进行置换 [first, last) 总共n!排列(假设所有元素都是唯一的)。

可以写这样的函数吗:

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

这会排列范围内的元素 [第一,最后] 但只选择范围内的元素 [first, choice_last) 也就是说,我们可能有20个元素,想迭代其中10个选项的所有排列,20P10个选项对20P20个选项。

• Iter是一个随机访问迭代器,但如果它可以实现为双向迭代器,那就太好了!
• 所需的外部内存越少越好,但就我的目的而言,这并不重要。
• 每次迭代中选择的元素被输入到序列的第一个元素中。

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

以下是我为解决这个问题所做的基本工作。我们也欢迎就如何改进这一点提出建议。

• 从向量开始 V 属于的 N 我想访问的每个排列的元素 R 从中选择的元素( R <= N ).
• 构建一个向量 I 长度 R 有价值观 { 0, 1, 2, ... R - 1 } 作为元素的索引 五、
• 在每次迭代中,构建一个向量 C 长度 R 有价值观 { V[I[0]], V[I[1]], ... V[I[R - 1]] }
• 用中的值做点什么 C .
• 应用一个函数来置换以下元素 一、 如果可以的话,再次迭代。

该函数看起来像这样:

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

此外,还有一种以类似方式工作的组合算法。然而,其实施要复杂得多。