数组所有排列的算法【基于盗梦空间】

    前些日子遇到一个算法面试题，需要求出一个数组的所有排列方式，个人所运用到的迭代递归算法与电影的“梦中梦”神似，有感而发。
    在每一次做梦之前，先预想好一个状态，在每一个梦做完之后，就需要恢复到我们做这一个梦之前的状态，因为在我们意识中的状态还是最初的状态，就像在递归之前改变数组的排列，递归完毕之后再恢复到这一次递归之前的状态。而我们并不知道我们的梦境处于第几层，于是我们需要一个标识来提供我们现在所处的位置。

	//一个泛型数组的空杯交换
	public static <T> void temp(T[] arr,int index1,int index2){
		T temp;
		temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}	
	/**
	 * 迭代递归
	 * @param <T> 泛型
	 * @param arr 泛型数组
	 * @param flag 标识符,用以标识从第几个元素开始迭代递归,元素从0开始
	 */
	public static <T> void sortAll(T[] arr,int flag){
		if(flag == arr.length){
			System.out.println(Arrays.toString(arr));
		}else{
			for (int i = flag; i < arr.length; i++) {
				temp(arr, i, flag);//迭代之前的空杯交换
				sortAll(arr, flag+1);//递归,将当前的标记自增
				temp(arr, i, flag);//迭代之后恢复原貌
			}
		}
	}
	//测试
	public static void main(String[] args) {
//		Integer[] arr = {1,2,2,3,4};
		Object[] arr = {'a','b','c'};
		sortAll(arr,0);
	}
}

评论

5 楼 panpan123mail 2011-05-14  

嗯，很不错，有感而发的算法。。。都把生活融入代码中是多么惬意的事。。。O(∩_∩)O~

4 楼 lyl290932857 2011-05-10  

都是高手，发现我越来越菜啊

3 楼 Scooler 2011-04-30  

public static <T> void temp(T[] arr, int index1, int index2) {
		if(index1 == index2)
			return;
		T temp;
		temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}

稍微说点小意见.这里加一句在10位以上的能提高30%的效率。。

2 楼 kaitian521 2011-04-30  

STL next_permutation（）

1 楼 uncoseason 2011-04-18  

在进行递归的前一行可以加上自己的过滤规则然后continue直接进入下一次的迭代。
例如:第一位不能为3,2的后一位不能是3

for (int i = flag; i < arr.length; i++) {
	temp(arr, i, flag);//迭代之前的空杯交换
           if(flag==0&&(Integer)arr[flag]==3)continue;//第一位不能为3
         //当前元素不是首位,2的后一位不能是3
         if(flag!=0)if((Integer)arr[flag]==3&&(Integer)arr[flag-1]==2)continue;
	sortAll(arr, flag+1);//递归,将当前的标记自增
	temp(arr, i, flag);//迭代之后恢复原貌
}