全排列算法(无重复元素时) --Java

public class Permutation { public static void permulation(int[] list, int start, int length) { int i; if (start == length) {//交换到最后一个数之后，start+1会等于length，这时输出list for (i = 0; i < length; i++) System.out.print(list[i] + " "); System.out.println(); } else { //！！递归 for (i = start; i < length; i++) { swap(list, start, i); permulation(list, start + 1, length); swap(list, start, i);//每轮递归结束负责把list调成原来的样子再继续递归 } } } //交换list中指定位置的元素 public static void swap(int[] list, int start, int i) { int temp; temp = list[start]; list[start] = list[i]; list[i] = temp; } public static void main(String[] args) { int length = 3; int start = 0; int list[] = new int[length]; for (int j = 0; j < length; j++) list[j] = j + 1; permulation(list, start, length); } } 思路：

关键的就是permulation方法的else里面的内容

（以求list[] = {"a","b","c"}的排列为例子）：

用i从list做一遍循环：

每一次循环中，都要将list[i]与list[start]互相调换位置：第一次开始，"a"与自己换，这时候，递归调用permulation[list,start + 1, length]

这是在求取list[start+1...length - 1]的排列即"b","c"的排列；

第二次，"a"与"b"互相调换，递归调用permulation[list,start + 1, length]就是在求取{"a","c"}的排列。

第三次，"a"与"c"互相调换，递归调用permulation[list,start + 1, length]就是在求取"{"b","a}的排列。

下面再以"b","c"的排列求取为例：

首先还是做循环，第一次，"b"与自己调换，这时候，调用permulation[list,start + 1, length], 就是求c的排列。

c与自己调换后，再调用permulation[list,start + 1, length]，这时候终于到了函数递归调用的出口了

start= length。输出a b c

第二次，类似的，输出a c b

至此，"b" "c"的排列求取完毕。

输出完以a开头的全排列，还要swap(list,i,start),目的是把list再调整回 a,b,c否则现在list就变成a c b了

类似的，就可以输出所有的排列了。

以list[3]={1,2,3}为例。

先是123，然后1与1自己对换，递归排列23，2与2自己对换，递归排列3，然后3与3对换，再递归时start+1满足start==length，即越界，所以把123打印出来；然后上一步2与2自己对换后，2与3对换，（暂时是132），递归到2与2对换，再递归满足start==length，打印132；输出完以1开头的全排列，还要swap(list,i,start),目的是把list再调整回 1,2,3 否则现在list就变成1 3 2了最先一步1与1自己对换后，1与2对换，（暂时是213），递归排列13，1与1自己对换，递归排列3. 3与3自己对换，然后满足If条件打印213：然后退一步，1与3对换，（暂时是231），递归到1与1自己对换，再递归满足打印条件，打印231;1与1、2对换后，1最后与3对换，（暂时是321），递归排列21，2与2对换，递归排列1.1与1自己对换，后来满足打印条件打印321. 2再与1对换，再递归到2与2自己对换，后来打印出312.

下面这种方法其实和上面的一样，只是在出口的地方有点不同，这个稍稍好理解一点

public List<List<Integer>> permute(int[] num) { List<List<Integer>> res = new LinkedList<List<Integer>>(); if(num == null || num.length < 1) return res; bt(res, 0, num); return res; } public void bt(List<List<Integer>> res, int now, final int[] num){ int length = num.length; if(now >= length) { res.add(new ArrayList<Integer>(){ { for(int i: num) add(i); } }); return ; } for(int i = now; i < length; i++){ swap(num, now, i); bt(res, now + 1, num); swap(num, now, i); } } public void swap(int[] nums, int idx1, int idx2){ int temp = nums[idx1]; nums[idx1] = nums[idx2]; nums[idx2] = temp; }