java - 给定 n 和 k,返回第 k 个排列序列

标签 java algorithm data-structures permutation backtracking

集合 [1,2,3,…,n] 一共包含 n 个!独特的排列。

通过按顺序列出和标记所有排列, 我们得到以下序列(即,对于 n = 3 ):

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321” 给定 n 和 k,返回第 k 个排列序列。

例如,给定 n = 3,k = 4,ans = "231"。

有多种解决方案。但是它们都使用阶乘,或者复杂度大于 O(n),例如 O(n!)。如果您使用阶乘并通过 k/(n-1)! 找到该位置的数字,那么当 n 很大时(n = 100)就会出现问题。这里 n 很大,(n-1)!溢出并变为 0。结果,我得到一个除以零的错误......有任何解决方案或算法吗?

这是我的代码:

public class KthPermutation {
    public String getPermutation(int n, int k) {
        // initialize all numbers
        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {
            numberList.add(i);
        }
        int fact = 1;   // set factorial of n-1

        for (int i = 1; i <= n-1; i++) {
            fact = fact * i;
        }   

        if ((long) k > (long) fact * n) {
            k = (int) ((long) k - (long) (fact * n));
        }
        k--; // set k to base 0

        StringBuilder result = new StringBuilder();
        result = getP(result, numberList, n, k, fact);
        return result.toString();
    }
    public static StringBuilder getP(StringBuilder result,
                ArrayList<Integer> numberList, int n, int k, int fact) {    
        if (numberList.size() == 1 || n == 1) {
            result.append(numberList.get(0));
            return result;  // return condition
        }
        int number = (k / fact) + 1 ;
        result.append(numberList.get(number - 1));
        numberList.remove(number - 1);
        k = k % fact;  // update k
        fact = fact / (n - 1);
        n--;
        return getP(result, numberList, n, k, fact);
    }
}

最佳答案

因此,如果我正确阅读了问题,您希望找到第 k 个排列,最好不使用 BigIntegers,前提是 k 不够大而需要 BigInteger。

如果我们看一下序列

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

我们可以重写它,使每个位置的数字成为该行迄今为止尚未出现的数字列表的索引:

0 0 0
0 1 0
1 0 0
1 1 0
2 0 0
2 1 0

例如“2, 0, 0”表示从列表“1, 2, 3”开始,然后取第三个(因为我们是从零开始索引),即3,然后取第一个剩余数字“1, 2”是1,然后是剩余数字的第一个,即“2”。所以它产生“3,1,2”。

要生成这些索引,请从右到左将 k 除以 1!最右边的两个地方,然后是 2!然后3!然后4!等,然后将结果与该位置的可能索引数取模,最右边为 1,最右边为 2,等等。您不必每次都计算阶乘,因为您可以保持正在运行的产品.

只要 k 除以阶乘为零,您就可以跳出循环,因此您只需计算阶乘,直到大约 k 的大小乘以 k 除以阶乘为非的最后一个位置零。如果 k 太大,则需要切换到 BigIntegers。

一旦有了索引,就可以很简单地使用它们来生成排列。

代码(k从0开始,所以找第一遍是0,不是1):

static public void findPermutation(int n, int k)
{
    int[] numbers = new int[n];
    int[] indices = new int[n];

    // initialise the numbers 1, 2, 3...
    for (int i = 0; i < n; i++)
        numbers[i] = i + 1;

    int divisor = 1;
    for (int place = 1; place <= n; place++)
    {
        if((k / divisor) == 0)
            break;  // all the remaining indices will be zero

        // compute the index at that place:
        indices[n-place] = (k / divisor) % place;
        divisor *= place;
    }

    // print out the indices:
    // System.out.println(Arrays.toString(indices));

    // permute the numbers array according to the indices:
    for (int i = 0; i < n; i++)
    {
        int index = indices[i] + i;

        // take the element at index and place it at i, moving the rest up
        if(index != i)
        {
            int temp = numbers[index];
            for(int j = index; j > i; j--)
               numbers[j] = numbers[j-1];
            numbers[i] = temp;
        }
    }

    // print out the permutation:
    System.out.println(Arrays.toString(numbers));
}

Demo

输出:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

n = 100 的第 10000000 次排列:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 92, 98, 96, 90, 91, 100, 94, 97, 95, 99, 93]

关于java - 给定 n 和 k,返回第 k 个排列序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31216097/

相关文章:

java - HashMap put()API时间复杂度

mysql - 带有加权分数的 Sql 流行度算法

java - 我自己的quicksort版本似乎仅适用于小型阵列

java - 来自 Java 的慢速系统命令

java - 是否可以设计一个递归来控制输出结果?

java - 如何将普通文件和文件夹包含到 Eclipse 产品/插件中?

data-structures - 全黑节点的树是红黑树吗?

java - 有关Java节点的基本知识

java - RXJava2中几种方法的组合

java - 将 jar 部署到 unix 服务器