java - 需要解释排列算法的差异

Question

我目前正在解决一个问题，要求我找到 0,1,2,3,4,5,6,7,8,9 的百万分之一字典排列。乍一看，我想到了一个非常粗糙的解决方案，其复杂度约为 O(n^3)

    public static String permute(char[] a){
        ArrayList<String> array = new ArrayList<String>(); 
        int counter = 1; 
        for (int i = 0; i < a.length; i++){
            array[counter] += a[i];
            for (int j = 0; j < i; j++){
            array[counter] += a[j];
                for(int k = a.length; k > i; k--){
                array[counter] += a[k];}counter++;}
        }
    }

代码可能并不完美，但想法是选择一个数字，然后移动到数组的末尾。第二个数组在所选数字后面创建数字，第三个数组在它后面创建数字。这似乎是一个糟糕的算法，我记得过去的一个算法就是这样的。

    public static HashSet<String> Permute(String toPermute) {
        HashSet<String> set = new HashSet<String>();
        if (toPermute.length() <= 1 )
            set.add(toPermute);
        else {
            for (int i = 0; i < toPermute.length(); i++ )
                for (String s: Permute(toPermute.substring(0,i)+ toPermute.substring(i+1)))
                {
                    set.add(toPermute.substring(i,i+1)+s);}
        }
        return set;
    }

}

问题是这个算法使用无序集，我不知道它如何变得足够有序，以便我找到百万分之一的排列。除了它可能是 O(n^2) 这一事实之外，我也不知道它的复杂性，因为它调用自己 n 次然后取消堆叠。

Answer 1

关于您上面的代码的一般情况:

1. 您应该实现接口(interface)而不是具体类，即List<String> array = ... .与您的 Set 类似.
2. 数组从索引 0 开始，您的计数器从索引 1 开始。

最后，为了回答您的问题，有一种蛮力方法和一种使用数学中某些原理的更优雅的方法。看看这个site其中解释了这些方法。