C++ permutation排列算法详解(深入了解,一文学会)

排列就是一次对对象序列或值序列的重新排列。例如，“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，所以会生成字典序最小的排列。

本文作者原创，转载请附上文章出处与本文链接。

1 next_permutation()

是按照字典升序的方式生成的排列

该算法输入一组数组，打印出所有全排列。

#include 
#include
using namespace std;
 
int main(int argc, char** argv) {
	int a[4] = { 1,2,3,4 };
	sort(a, a + 4);
	do {
		//cout<
		for (int i = 0; i < 4; i++)
			cout << a[i] << " ";
		cout << endl;
	} while (next_permutation(a, a + 4));
	return 0;
}

2 prev_permutation()

是按照字典升序的方式生成的排列

#include 
#include
#include
using namespace std;
 
int main(int argc, char** argv) {
    std::vector<double> data{ 44.5, 22.0, 15.6, 1.5 };
    do {
        std::copy(std::begin(data), std::end(data), std::ostream_iterator<double> {std::cout, " "});
        std::cout << std::endl;
    } while (std::prev_permutation(std::begin(data), std::end(data)));
	return 0;
}

3 is_permutation

#include 
#include
#include
 
 
using namespace std;
 
int main(int argc, char** argv) 
{
    std::vector<double> data1{ 44.5, 22.0, 15.6, 1.5 };
    std::vector<double> data2{ 22.5, 44.5, 1.5, 15.6 };
    std::vector<double> data3{ 1.5, 44.5, 15.6, 22.0 };
    auto test = [](const auto& d1, const auto& d2)
    {
        std::copy(std::begin(d1), std::end(d1), std::ostream_iterator<double> {std::cout, " "});
        std::cout << (is_permutation(std::begin(d1), std::end(d1), std::begin(d2), std::end(d2)) ? "is" : "is not") << " a permutation of ";
        std::copy(std::begin(d2), std::end(d2), std::ostream_iterator<double>{std::cout, " "});
        std::cout << std::endl;
    };
    test(data1, data2);
    test(data1, data3);
    test(data3, data2);
 
 
	return 0;
}