排列算法 C++实现

浏览数：21 / 时间：2015年06月08日

1.什么是排列？

排列的任务是确定 $\text{[math]}$ 个不同的元素的排序的可能性。从下边的示意图可看出，3个不同颜色的彩球一共有6种不同的排列方式，因此有如下定理：“ $\text{[math]}$ 个不同的元素可以有 $\text{[math]}$ 种不同的排列方式，即 $\text{[math]}$ 的阶乘。”因此上面的例子的算法是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 <iostream>

using namespace std;

template <class T>
inline void Swap(T& a, T& b)
{// 交换a和b
	T temp = a; a = b; b = temp;
}

template<class T>
void 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;
}

结果如下：