《算法之美》の递归与分治策略の全排列问题

全排列问题：设R={r1, r2, …, r3}是要进行排列的n个元素，Ri = R – {ri}。集合X中元素的全排列记为Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri，得到的排列。

因此，R的全排列可以归纳定义如下：

1）当n=1时，Perm(R) = (r)，其中r是集合R中唯一的元素；

2）当n>1时，Perm(R)由：(r1)Perm(R1)，(r2)Perm(R2)，…，(rn)Perm(Rn)构成。

我们据此设计递归算法如下：

#include <iostream>

/**

* 功能描述：交换两个数的值

* 参数：

* a---数一

* b---数二

*/

template<typename T>

void swap(T &a, T &b)

{

T temp = a;

a = b;

b = temp;

}

/**

* 功能描述：全排列

* 参数：

* data[]---待排列的数组

* k---开始排列的元素在数组中的下标

* m---结束排列的元素在数组中的下标

*/

template<typename T>

void ASCEPerm(T data[], int k, int m)

{

//产生data[k:m]的所有排列

if(k == m)//单元素排列，递归的结束条件

{

for(int i=0; i<=m; i++)

{

std::cout<<data[i];

}

std::cout<<std::endl;

} else {

for(int i=k; i<=m; i++)

{

swap(data[k], data[i]);

ASCEPerm(data, k+1, m);

swap(data[k], data[i]);

}

}

}

int main()

{

int data[] = {1, 2, 2};

ASCEPerm<int>(data, 0, 2);

system("pause");

return 0;

}

算法Perm(data, k, m)递归地产生所有前缀是data[0:k-1]，且后缀是data[k:m]的全排列的所有排列。函数调用Perm(data, 0, n-1)则产生data[0:n-1]的全排列。

在一般情况下，k<m。算法将data[k:m]中每一个元素分别与data[k]中元素交换；然后递归计算data[k+1:m]的全排列，并将计算结果作为data[0:k]的后缀。