C++ STL next_permutation算法如何实现长尾词的排列生成？

本文共计1763个文字，预计阅读时间需要8分钟。

排序就是将一组对象（如对象序列或值序列）重新排列成指定的顺序。例如，ABC中字符可能的排列有：ABC、ACB、BAC、BCA、CAB、CBA，三个不同字符共有6种排列，这个数字是3×2×1得到的。一般来说，n个不同的字符有n!种排列。

排列就是一次对对象序列或值序列的重新排列。例如，“ABC”中字符可能的排列是：

"ABC", "ACB", "BAC", "BCA", "CAB", "CBA"

三个不同的字符有 6 种排列，这个数字是从 3*2*1 得到的。一般来说，n 个不同的字 符有 n! 种排列，n! 是 nx(n_1)x(n-2)...x2x1。很容易明白为什么要这样算。有 n 个对象 时，在序列的第一个位置就有 n 种可能的选择。对于第一个对象的每一种选择，序列的第 二个位置还剩下 n-1 种选择，因此前两个有 nx((n-1) 种可能选择。在选择了前两个之后， 第三个位置还剩下 n-2 种选择，因此前三个有 nx(n-1)x(n-2) 种可能选择，以此类推。序列的末尾是 Hobson 选择，因为只剩下 1 种选择。

对于包含相同元素的序列来说，只要一个序列中的元素顺序不同，就是一种排列。next_permutation() 会生成一个序列的重排列，它是所有可能的字典序中的下一个排列，默认使用 < 运算符来做这些事情。它的参数为定义序列的迭代器和一个返回布尔值的函数，这个函数在下一个排列大于上一个排列时返回 true，如果上一个排列是序列中最大的，它返回 false，所以会生成字典序最小的排列。