JAVA置换生成器方法分析.

Question

我一直在尝试分析这个用于排列生成的 JAVA 程序。我知道在算法中，时间复杂度是O(n*n！(和O(n(，因为它需要它打印一个排列。有人可以进一步解释下面对实现的分析吗？

import java.util.*;
public class Permutation
{
public static void main(String[] args) throws Exception {
List<Integer> intList = new ArrayList<Integer>();
intList.add(1);
intList.add(2);
intList.add(3);
List<List<Integer>> myLists = listPermutations(intList);
for (List<Integer> al : myLists) 
{
String appender = "";
for (Integer i : al) 
{
System.out.print(appender + i);
appender = " ";
}
System.out.println();
}
}

public static List<List<Integer>> listPermutations(List<Integer> list) 
{
if (list.size() == 0) 
{
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(new ArrayList<Integer>());
return result;
}
List<List<Integer>> returnMe = new ArrayList<List<Integer>>();
Integer firstElement = list.remove(0);
List<List<Integer>> recursiveReturn = listPermutations(list);
for (List<Integer> li : recursiveReturn) 
{
for (int index = 0; index <= li.size(); index++) 
{
List<Integer> temp = new ArrayList<Integer>(li);
temp.add(index, firstElement);
returnMe.add(temp);
}
}
return returnMe;
}
}
//end Java program 

Answer 1

以下是它如何工作的描述：

remove the first element
get all permutations of the remaining elements (recursively)
for each position in each permutation
insert the first element at that position in that permutation 

使用示例

permutations of [a, b, c]
remove a
permutations of [b, c]
remove b
permutations of [c]
remove c
permutations of []
= [[]]
for each, insert c in each position
=[[c]]
for each, insert b in each position
=[[b,c], [c,b]]
for each, insert a in each position
= [[a,b,c], [a,c,b], [b,a,c], [c,a,b], [b,c,a], [c,b,a]]

计算 n 个元素的排列需要计算 n-1 个元素的排列(递归调用(，然后对其进行 n 次处理(插入(。对于 n-1 也是如此，依此类推，直到 0 需要常量时间 (1(。因此 O 是 n * n-1 * n-2 ...1 或 n！。