设 R={ r1, r2, ... , rn} 是需要排列的 N 个元素。Ri = R - { ri } 。 设集合 中的元素 全排列记 为 Perm(X) ;
(ri)Perm(X) 表示在 全排列 Perm(X)的每一个排列前加上前缀 ri 得到的全排列。
例如在 Perm(X) 的排列为 Perm(X)={ 2 ,1} ,在 Perm(X) 加前缀 ri= 3 ,即得到 riPerm(X) ={ 3 ,2 ,1} 。
R 的全排列可以定义为：
（1） 当 n=1 时 Perm( R) =(r1） ，r1 是 R 中唯一的元素。
（2） 当 n > 1 时 Perm(R) 由 （r1)Perm(R1) , (r2)Perm(R2) , .... , (rn)Perm(Rn) 构成。
例如：
R = { 1 , 2 , 3}
step1: 1 {2,3 } , 2{1,3} , 3{ 2,1}
/// 接下来 是将 长度为 2 的 子问题 继续划分。
step2: 2{3} , 1{3} , 2{1} // 直到R 被分成 只含1 个元素时就技术 划分。
step3: 3{2} , 3{1} , 1{2}
接下来可以依次加上前缀：
可以得到： {1, 2, 3} ， {2,1,3} , {3,2,1}
{1,3,2} , {2,3,1} , {3,1,2} ///
#include<iostream> #include<cstdio> using namespace std; void Swap(int &a,int &b) { int temp = a; a=b; b=temp; } void Perm(int R[],int low,int m) { if(low==m){ for(int i=0; i<=m; i++) cout<<R[i]<<" "; cout<<endl; } else for(int i=low; i<=m; i++){///与第一个元素进行交换 Swap(R[low],R[i]); Perm(R,low+1,m);///交换后的子序列在交换，low+1位置 到 序列尾 Swap(R[low],R[i]); } } int main() { int n; int R[1000]; cin>>n; for(int i=0; i<n; i++ ) cin>>R[i]; Perm(R,0,n-1); return 0; }
