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!.

JAVA的排列生成器方法分析

Analysis of permutation generator method for JAVA

java

permutation

analysis