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

标签 java algorithm complexity-theory permutation

我目前正在解决一个问题,要求我找到 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 次然后取消堆叠。

最佳答案

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

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

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

关于java - 需要解释排列算法的差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15257043/

相关文章:

c - 需要解释此代码(算法)

time-complexity - 什么是近似因子?

java - 如何删除 "Linear Layout"中的渐变边框?

Java收集列表但指定预定义的前两个元素顺序

java - 插入后获取生成的id

c - 为什么我的 C 中的链表失败了?

c# - 排序对象列表的算法

c++ - dfa 转换函数

security - DoD 密码复杂性 : Users cannot reuse any of their previous X passwords

java - 如何在不同应用程序之间通过请求发送对象