排列算法 C++实现

排列算法 C++实现

1.什么是排列？

排列的任务是确定

个不同的元素的排序的可能性。从下边的示意图可看出，3个不同颜色的彩球一共有6种不同的排列方式，因此有如下定理：“

个不同的元素可以有

种不同的排列方式，即

的阶乘。”因此上面的例子的算法是3 ! = 6。

为什么是3的阶乘呢？因为第一个位置有3种颜色可选，除去第一个位置，第二个位置就只有2种颜色可选了，确定好第一位置和第二个位置，第三个位置自动就确定下来了，故一共有3*2*1种可能就是3的阶乘，6种可能。

2.计算机中的C++实现

这个其实是一个蛮难的问题，最普遍的是用递归实现，不过递归效率比较低。

// Perm.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include using namespace std;template inline void Swap(T& a, T& b){// 交换a和b T temp = a; a = b; b = temp;}templatevoid Perm(T list[], int k, int m){ //生成list [k：m ]的所有排列方式int i;if (k == m) {//输出一个排列方式 for (i = 0; i <= m; i++) cout << list [i]; cout << endl;}else // 每次交换产生一个新排列for (i=k; i <= m; i++) { Swap (list[k], list[i]); Perm (list, k+1, m); Swap (list[k], list[i]); }}int _tmain(int argc, _TCHAR* argv[]){ int a[3] = {1, 2, 3}; Perm(a,0,2); system("pause"); return 0;}

结果如下：

老实说，这样写是能出结果，但是可能是我脑子不好使，竟然看不懂，递归的代码特别不容易看懂。后面很努力地看了下，解释如下：

数学中我们知道求1，2，3的排列，第一个位置有3中可能，即1，2，或者3。给人的感觉是物理的感觉，从1，2，3中，每次取一个。这样在计算机中很难表达，在计算机中，有个简便的处理手段，就是交换，跟自己包括后面所有的数交换一次就行了，即得到

1，2，3； // 1 跟 1交换

2，1，3； // 1 跟 2 交换  (又是从1，2，3开始，所以每次交换完都要交换回去，复原)

3，2，1 ；// 1 跟 3 交换  又是从1，2，3开始，所以每次交换完都要交换回去，复原)

上面的代码又有这样的意思：总共的可能又变成 1 + (2,  3)的排列，2 + (1,  3)的排列， 3 + (2, 1)的排列。  那如何求 2，3的排列呢？ 又是交换，2跟2交换，2跟3交换。 1，3 和 2，1是同样道理。

这样一共是3 * 2 共 6 种可能。

3.stl中的next_permutation

递归的效率是很低的，我们注意到Stl中有个叫next_permutation的函数，它可以返回下一个值，比如1，2，3。 它会返回1，3，2。1，3，2 究竟是什么意思？它是怎么实现的呢？

举例一个较长的数组吧，1，5，4，7，6，3。 我们把它看成一个六位数，就是154763。 那么下一个值，由1，3，4，5，6，7 这 6个数字组成且比 154763 大，那么就是156347。然后再求156347的下一个值就是156374，不断往下求，也能得到所有的排列组合。

1，2，3 就是:  123 < 132 < 213 < 231 < 312 < 321。

4.如何求下一个数比当前大呢？

我们知道数字的权重从个位数开始增加，我们来看下154763的154763，4和6 。 从个位开始查找，6是第一个比4大的数，且4的位数比6大，如果交换这两个数，总的值就会变大。

我们的策略如下：

1.从个位开始往前查找，找到第一个逆序的值，154763中就是4。

2.再从个位开始往前查找，找到第一个比刚才逆序值大的数，这里就是6。

3.交换两个数最后会得到156743，我们发现156743并不是我们想要的数，因为156743比156347要大。

4.所以我们最后一步就是要对743进行排序，排成最小的347

5.有特殊情况，比如刚开始的数就是全逆序的，比如765431，那么下一个值是134567.

bool nextPermutation(vector& num){ int beforeIndex = 0; //记录逆序值的索引 int currentIndex; bool isAllReverse = true; //找到第一个逆序的索引 for(currentIndex = num.size() - 1; currentIndex > 0; --currentIndex){ beforeIndex = currentIndex - 1; if(num[beforeIndex] < num[currentIndex]){ isAllReverse = false; break; } } //如果找不到一个，说明这个数组本来就是逆序的 if(isAllReverse){ sort(num.begin(), num.end()); return false; }else{ //再从后面找第一个比逆序值大的数 int firstLargeIndex = 0; for(firstLargeIndex = num.size() - 1; firstLargeIndex > beforeIndex; --firstLargeIndex){ if(num[firstLargeIndex] > num[beforeIndex]){ break; } } //交换他们 swap(num[beforeIndex], num[firstLargeIndex]); //剩余的进行从小到大排序 sort(num.begin() + beforeIndex + 1, num.end()); return true; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。