本文共 2810 字，大约阅读时间需要 9 分钟。
问题描述
给定一个整型数组，例如：[1,2,3]，输出元素的全排列形式，即：
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]算法分析
当只有一个元素时，集合为：{1}
现在加入2，将数字2分别加入上述集合的 0位置和1位置， 可以得到：{2，1}；{1，2} 当在加入3时， 可以将数字3分别插入集合{2,1}，和集合{1,2}的 0，1，2位置 对于集合{2,1}，数字3插入的位置为0时，得到{3，2，1}；数字3插入的位置为1时，得到{2，3，1}；数字3插入的位置为2时，得到{2，1，3} 对于集合{1,2}，数字3插入的位置为0时，得到{3，1，2}；数字3插入的位置为1时，得到{1，3，2}；数字3插入的位置为2时，得到{1，2，3}两个集合，可以选择3个插入位置：2*3 = 6，全排列为6种。
最终得到：{3，1，2}；{3，2，1}；{1，3，2}；{2，3，1}；{1，2，3}；{2，1，3}
算法设计
给出第一种算法设计
public List
> permute(int[] num) { List
> ans = new ArrayList
>(); if (num.length ==0) return ans; List l0 = new ArrayList (); l0.add(num[0]); ans.add(l0); for (int i = 1; i< num.length; ++i){ List
> new_ans = new ArrayList
>(); for (int j = 0; j<=i; ++j){ for (List l : ans){ List new_l = new ArrayList (l); new_l.add(j,num[i]); new_ans.add(new_l); } } ans = new_ans; } return ans; }
完整的代码如下：
package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.List;public class PermutationsDemo2 { public List > permute(int[] num) { List > ans = new ArrayList >(); if (num.length ==0) return ans; List l0 = new ArrayList (); l0.add(num[0]); ans.add(l0); for (int i = 1; i< num.length; ++i){ List > new_ans = new ArrayList >(); for (int j = 0; j<=i; ++j){ for (List l : ans){ List new_l = new ArrayList (l); new_l.add(j,num[i]); new_ans.add(new_l); } } ans = new_ans; } return ans; } public static void main(String[] args) { // TODO Auto-generated method stub PermutationsDemo2 pd=new PermutationsDemo2(); int[] array= { 1,2,3}; List > list=pd.permute(array); System.out.println(list); }}
给出第二种算法设计
package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.List;public class PermutationsDemo { public List > permute(int[] nums) { List > permutations = new ArrayList<>(); if (nums.length == 0) { return permutations; } collectPermutations(nums, 0, new ArrayList<>(), permutations); return permutations; } private void collectPermutations(int[] nums, int start, List permutation, List > permutations) { if (permutation.size() == nums.length) { permutations.add(permutation); return; } for (int i = 0; i <= permutation.size(); i++) { List newPermutation = new ArrayList<>(permutation); newPermutation.add(i, nums[start]); collectPermutations(nums, start + 1, newPermutation, permutations); } } public static void main(String[] args) { // TODO Auto-generated method stub PermutationsDemo pd=new PermutationsDemo(); int[] array= { 1,2,3}; List > list=pd.permute(array); System.out.println(list); }}
（完）
转载地址：http://cwtdi.baihongyu.com/