1

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

4

3 回答 3

0

在我看来（1）哪个排列是百万分之一绝对取决于您使用的顺序，并且（2）这种排列是递归的成熟问题。我会把它写成一个递归程序，并为每次迭代增加计数。[那是你的问题吗？我真的没有看到问题...]

于 2013-03-06T20:22:18.263 回答
0

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

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

最后，要回答您的问题，有一种蛮力方式和一种更优雅的方式，它在数学中使用了一些原则。看看这个解释这些方法的网站。

于 2013-03-06T20:23:27.997 回答
0

这是一个更有效的解决方案：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P24 {

    static final int digits[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    static List<Integer> remainedDigits = new ArrayList(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
    static final int factorials[] = new int[digits.length + 1];
    static final int N = 1000_000;

    static int low = -1;
    static int lowIndex = -1;
    static int highIndex = -1;

    public static void main(String args[]) {
        populateFactorials(digits.length);
        validateN(N);
        identifyMargins();
        int n = N;  // it will be changed

        int fixedDigits = digits.length - highIndex;

        String result = "";
        for (int i = 0; i < fixedDigits; i++) {
            result += remainedDigits.get(0);
            remainedDigits.remove(0);
        }

        for (int i = fixedDigits; i < digits.length; i++) {
            int pos = 0;
            int firstDigit = remainedDigits.get(pos);
            low = factorials[lowIndex];
            while (n - low > 0) {
                pos++;
                n -= low;
            }
            lowIndex--;
            result += remainedDigits.get(pos);
            remainedDigits.remove(pos);
        }

        System.out.println(result);
    }

    private static void validateN(int n) {
        if (n < 0 || n > factorials[factorials.length - 1]) {
            System.out.println("The input number is not valid");
            System.exit(0);
        }
    }

    private static void identifyMargins() {
        for (int i = 0; i < factorials.length - 1; i++) {
            if (factorials[i] <= N && N < factorials[i + 1]) {
                lowIndex = i;
                highIndex = i + 1;
            }
        }
    }

    private static void populateFactorials(int max) {
        for (int i = 0; i <= max; i++) {
            factorials[i] = fact(i);
        }
    }

    private static int fact(int x) {
        if (x == 0 || x == 1) {
            return 1;
        }
        int p = 1;
        for (int i = 2; i <= x; i++) {
            p *= i;
        }
        return p;
    }

}

时间：305 微秒。

解释：

  1. 因为排列的总数{a1, ..., an}是n!，所以我决定需要一个factorials数组。我存储在其中：{0!, ..., 10!}.
  2. 我确定了这个序列中的数字在哪里，对于我们的例子（N = 1000000），它在9!和之间10!。如果它低于我添加从数组中获取9!的数字填充。fixedDigitsremainedDigits
  3. 因为数字大于9!，所以我数了数我可以从数字中提取多少次9!，结果帮助我获得第一个数字。8!然后，我对,7!等有类似的方法。

上述解释基于以下简单观察。如果我们有一个集合{a1,...,ai,...,an}并且我们修复a1, ..., ai，我们可以获得(n-i)!不同的字符串。

请注意，如果您使用：

static List<Integer> remainedDigits = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);

您不能从列表中删除元素。`

于 2014-11-26T23:18:41.333 回答