全排列算法

方法一：

 

将n的全排列转化为n-1的全排列，递归完成：

 

  
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
  
/** 
 * <p> 
 * Title:全排列算法 
 * </p> 
 * 
 */  
public class AllSort {  
    //将NUM设置为待排列数组的长度即实现全排列  
    private static int NUM = 4;  
  
    private static void sort(List datas, List target) {  
        if (target.size() == NUM) {  
            for (Object obj : target)  
                System.out.print(obj);  
            System.out.println();  
            return;  
        }  
        for (int i = 0; i < datas.size(); i++) {  
            List newDatas = new ArrayList(datas);  
            List newTarget = new ArrayList(target);  
            newTarget.add(newDatas.get(i));  
            newDatas.remove(i);  
            sort(newDatas, newTarget);  
        }  
    }  
  
    public static void main(String[] args) {  
        String[] datas = new String[] { "a", "b", "c", "d" };  
        sort(Arrays.asList(datas), new ArrayList());  
    }  
  
}  

 方法二，dfs深度遍历，利用数组记录访问历史，无需像上例动态remove链表

 

public class DfsFullSort {
	private int[] a = {1,2,3};
	private boolean[] vis = {false,false,false};
	private int n = 3;
	
	public static void main(String[] args) {
		DfsFullSort sort = new DfsFullSort();
		sort.dfs(0,"");
	}

	private void dfs(int step,String s) {
		if (step == a.length) {
			System.out.println(s);
			return;
		}
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				vis[i] = true;
				String t =s;
				s = s + a[i];
				dfs(step + 1,s);
				s= t;
				vis[i] = false;
			}
		}
	}
}