枚举法求全排列

问题描述：

输入整数N，按照字典序从小到大打印出1-N的去所有排列。两个序列的字典序大小关系等价于从头开始第一个不相同处的大小关系，（例如(1,2,3)<(3,2,1)），N=3时，输出结果是：(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1).

 

算法思想：

设集合S是保持带排列元素的集合，数组A保持排列的元素。

如果集合S为空，则表示完成了一个排列，不再继续递归，否则将S中的元素V加入到A中，且S = S-{V}，继续递归寻找下一个可以加入到排列中的元素。伪代码如下：

 

 

Status print_permutation(序列A，集合S)
{
        if(S==空集)
        {
              打印A
        }
        else 从小到大依次尝试将S中的元素加入序列A
        {
              print_permutation(加入元素后的新序列A,S-{V});
        }
}

按照如上伪代码，不难写出如下程序：

#include<iostream>
using namespace std;
//枚举全排列的函数
//n表示元素总个数，A表示当前序列，cur表示当前元素个数 
void Print_Arrangement(int n,int *A,int cur)
{
     int i,j;
     if(n==cur)//如果一个排列完成了 
     {
        for(int i=0;i<n;i++)
        cout<<A[i];
        cout<<endl;
     }
     else for(int i=1;i<=n;i++)
     {
        int ok = 1;
        for(int j=0;j<cur;j++)
        {
           if(A[j]==i)
           ok = 0;
        }//元素是否已经在排列中出现过 
        if(ok)
        {
            A[cur] = i;
            Print_Arrangement(n,A,cur+1);
        }
     }
}
int main()
{
    //测试N=3的情况 
    int A[100];
    int n = 3;
    Print_Arrangement(n,A,0);
    system("pause");
    return 0;
}

下面考虑用处理字符排列的情况，如果是用char数组的话，只需将int数组改成char数组，并且用一个char数组保存待排列的 元素，实现代码如下：

package ScannerTest;
/**
 * 枚举全排列的类
 * @author dell
 *
 */
public class Permutation {

	/**
	 * 主函数
	 * @param args
	 */
	public static void main(String[] args){
		
		char[] container = {'1','2','3'};
		Permutation p = new Permutation(container);
		char[] now = new char[1000];
		p.Print_Permutation(3, now, 0);
	}
	
	/**
	 * 打印排列
	 * @param n
	 * @param now
	 * @param total
	 */
	public void Print_Permutation(int n,char[] now,int total){
		
		if(n==total){
			for(int i=0;i<n;i++){
				System.out.print(now[i]);
			}
			System.out.print("\n");
		}else for(int i=0;i<n;i++){
			
			char add = set[i];
			boolean ok = true;
			
			for(int j=0;j<total;j++){
				if(now[j]==add){
					ok = false;
				}
			}
			
			if(ok){
				now[total] = add;
				Print_Permutation(n,now,total+1);
			}
			
		}
		
	}
	
	public Permutation(char[] s){
		set = s;
	}
	
	
	//待排列集合
	private char[] set;
	
}

但是，如果用字符串String来处理的话，情况稍许不同，代码如下：

 

package ScannerTest;
/**
 * 枚举全排列的类
 * @author dell
 *
 */
public class Arrangement {
	/**
	 * 主函数
	 * @param args
	 */
	public static void main(String[] args){
		Arrangement ar = new Arrangement("123");
		String now = "";
		ar.Print_Arrangement(3, now, 0);
	}
	
	/**
	 * 构造函数
	 * @param str
	 */
	public Arrangement(String str){
		set = str;
	}
	
	/**
	 * 枚举全排列的函数
	 * @param n 总元素个数
	 * @param now 现在的排列
	 * @param total 当前元素个数
	 */
	public void Print_Arrangement(int n,String now,int total){
		
		//如果当前元素个数满足输出条件
		if(total==n){
			System.out.println(now);
		}else{
			//枚举下一步可能出现的每一种情况
			for(int i=0;i<set.length();i++){
				//加入排列的元素
				char add = set.charAt(i);
				boolean ok = true;
				for(int j=0;j<now.length();j++){
					if(now.charAt(j)==add){
						ok = false;
					}
				}
				//如果排列中不包含了该元素
				if(ok){
					now = now+add;
					Print_Arrangement(n,now,total+1);
					//这步非常关键，必须还原字符串
					now = now.substring(0,now.length()-1);
				}
			}
		}
		
	}
	
	

	private String set;//元素集合
}

如上代码，在递归寻找完元素后必须还原字符串！