递归实现排列算法

基本原理

N个元素排列，第1个位置有N种可能；第1个位置确定后，可将第2至第N个位置看作N-1个元素的排列；依此类推，可递归直至最后一个元素，为1个元素的排列。

实现代码
以下代码抄自http://blog.csdn.net/guo_rui22/article/details/2199732，略有改动，并添加注释。

import java.util.ArrayList;
/**
 * 全排列算法
 * 
 */
public class Arrange {

	private int total = 0;
	private ArrayList<String> arrangeList = new ArrayList<String>();

	public Arrange() {
	}

	/**
	 * 交换数组中两个元素的位置
	 * 
	 * @param list 待处理的元素数组
	 * @param m 要交换元素在数组中的位置
	 * @param n 要交换元素在数组中的位置
	 */
	private void swap(String list[], int m, int n) {
		String tmp = list[m];
		list[m] = list[n];
		list[n] = tmp;
	}

	/**
	 * 递归函数排列子数组（原始数组中位置从j到max）中的元素
	 * 
	 * @param list 原始数组
	 * @param j 子数组在原始数组中的位置
	 * @param max 原始数组长度
	 */
	public void perm(String list[], int j, int max) {
		// 递归结束，保存结果
		if (j > max) {
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i <= max; i++) {
				sb.append(list[i]).append(",");
			}
			if (sb.length()>0) {
				sb.setLength(sb.length()-1);
			}
			arrangeList.add(sb.toString());
			total++;
		} else {
			for (int i = j; i <= max; i++) {
				// 将子数组中元素i交换到当前子数组首位
				swap(list, j, i);
				// 排列首位以后的子数组
				perm(list, j + 1, max);
				// 将前面换到子数组首位的元素换回原位，以免影响其它子数组排列
				swap(list, j, i);
			}
		}
	}

	public int getTotal() {
		return total;
	}
	
	public ArrayList<String> getArrangeList() {
		return arrangeList;
	}

	public static void main(String args[]) {
		String list[] = { "1", "2", "3", "4", "5" };
		Arrange ts = new Arrange();
		ts.perm(list, 0, list.length-1);
		for (int i = 0; i < ts.getArrangeList().size(); i++) {
			System.out.println(ts.getArrangeList().get(i));
		}
		System.out.println("total:" + ts.total);
	}

}