排列问题

      设R={r∨1,r∨2,...,r∨n}是要进行排列的n个元素,R∨i=R-{r∨i}。集合X中元素的全排列记为perm(X)。(r∨i)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r∨i得到的排列。R的全排列可归纳定义如下：

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

       当n>1时，perm(R)由(r∨1)perm(R∨1),(r∨2)perm(R∨2),...,(r∨n)perm(R∨n)构成。

       依次递归定义，可设计产生perm(R)的递归算法如下:

     

public static void perm(Object [] list,int k,int m)
	{
		//产生list[k:m]的所有排列
		if(k==m)
		{
			//只剩一个元素
			for(int i=0;i<=m;i++)
				System.out.print(list[i]);
			System.out.println();
		}
		else
		//还有多个元素，递归产生排列
		for(int i=k;i<=m;i++)
		{
			MyMath.swap(list,k,i);
			perm(list,k+1,m);
			MyMath.swap(list,k,i);
			
		}
	}

 

 

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

        在一般情况下，k<m。算法将list[k:m]中每一个元素分别与list[k]中元素交换。然后递归地计算list[k+1:m]的全排列，并将计算结果作为list[0:k]的后缀，算法中MyMath.swap用于交换两个表元素值。