代码之家 › 专栏 › 技术社区 › RyanP

JAVA的置换生成器方法分析

analysis permutation java

RyanP · 技术社区 · 6 年前

我一直在尝试分析这个用于置换生成的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

1 回复 | 直到 6 年前

sprinter 6 年前

以下是对其工作原理的描述:

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