是的， 是 “下一个置换”的算法，这是相当简单了。C ++标准模板库（STL）甚至具有称为的功能next_permutation。

该算法实际上找到了 下一个 排列-从字典上看是下一个。这个想法是这样的：假设您得到一个序列，说“ 32541”。下一个排列是什么？

如果您考虑一下，就会看到它是“ 34125”。您的想法可能是这样的：在“ 32541”中，

• 没有办法固定“ 32”并在“ 541”部分中找到更高的置换，因为该置换已经是5,4和1的最后一个-降序排列。
• 因此，您必须将“ 2”更改为更大的值-实际上，将其更改为比“ 541”部分中更大的最小数字，即4。
• 现在，一旦您确定排列将以“ 34”开始，其余数字应按升序排列，因此答案为“ 34125”。

该算法将精确地实现这一推理：

1. 找到以降序排列的最长“尾巴”。（“ 541”部分。）
2. 将紧邻尾巴的数字（“ 2”）更改为大于尾巴的最小数字（4）。
3. 尾巴按升序排序。

只要前一个元素不小于当前元素，就可以从结尾开始并向后退，从而高效地执行（1.）。您只需将“ 4”与“ 2”交换即可完成（2.），因此您将拥有“
34521”。一旦执行此操作，就可以避免对（3.）使用排序算法，因为尾部过去（现在）（现在仍在思考）以降序排列，因此只需要反转即可。

C
代码正是这样做的（请查看系统中的源代码/usr/include/c++/4.0.0/bits/stl_algo.h或查看本文）。将其翻译成您的语言应该很简单：[如果您不熟悉C 迭代器，请阅读“
BidirectionalIterator”作为“指针”。false如果没有下一个排列，则代码返回，即我们已经处于降序状态。]

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

似乎每个排列可能花费O（n）时间，但是如果仔细考虑一下，您可以证明所有排列总共花费O（n！）时间，因此只有O（1）-恒定时间-排列。

好消息是，即使您的序列中包含重复的元素，该算法也可以工作：例如使用“ 232254421”，它将发现尾部为“ 54421”，交换“ 2”和“ 4”（因此“
232454221” ），反转其余部分，得到“ 232412245”，这是下一个排列。