如何求N个组合R中的第k项

本文介绍了如何求N个组合R中的第k项的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 如何在NCR中获取kth组合。而不需要迭代所有可能的结果。例如，假设我对3个位置和2个相同的项目有3C2个。我知道是[011]、[101]和[110]。例如，如何使用方法获取[101]的第二项(k=1)？

约束(R < Nk >= 0和k < PwhereP = NCR)。

NB：[101]是第二个术语(以升序/词典顺序)，因为011=3，101=5，110=6 以十进制表示。所以基本上目标是得到ncr中的k是多少， 因为NCR的每个kth输出都可以用数字表示。

推荐答案

时间复杂度为O(Kn)，空间复杂度为O(N)

public static void main(String[] args) { //n = 4, r = 2, k = 3 int[] ret1 = getKthPermutation(4, 2, 3); //ret1 is [1,0,0,1] //n = 3, r = 2, k = 1 int[] ret2 = getKthPermutation(3, 2, 1); //ret2 is [1,0,1] } static int[] getKthPermutation(int n, int r, int k) { int[] array = new int[n]; setLastN(array, r, 1); int lastIndex = n - 1; for(int count = 0; count < k; count++) { int indexOfLastOne = findIndexOfLast(array, lastIndex, 1); int indexOfLastZero = findIndexOfLast(array, indexOfLastOne, 0); array[indexOfLastOne] = 0; array[indexOfLastZero] = 1; //shortcut: swap the part after indexOfLastZero to keep them sorted int h = indexOfLastZero + 1; int e = lastIndex; while(h < e) { int temp = array[h]; array[h] = array[e]; array[e] = temp; h++; e--; } } return array; } //starting from `from`, and traveling the array forward, find the first `value` and return its index. static int findIndexOfLast(int[] array, int from, int value) { for(int i = from; i > -1; i--) if(array[i] == value) return i; return -1; } //set the last n elements of an array to `value` static void setLastN(int[] array, int n, int value){ for(int i = 0, l = array.length - 1; i < n; i++) array[l - i] = value; }

这是非常典型的"寻找第k个变形"算法的改编。

我将尝试解释一般概念(您的是一个特例，因为只有两种类型的元素：0和1)。 假设我有[2,1,6,4,7,5]。下一个最小的排列比现在的排列大的是什么？为什么我要关注比当前排列更大的下一个最小排列呢？因为如果您从最小的排列[1,2,4,5,6,7]开始，并将该操作重复k次(找到比当前大的最小的排列)，您将找到第k+1个最小的排列。

现在，由于我要查找的值需要大于当前值，因此需要递增当前值。为了使增量尽可能小，我将尝试修改5(最后一个)。现在，我不能只将5更改为随机值，我只能将其与其前面的某个数字交换。

如果我将5与前面的一个更大的数字交换，比如7，那么我将得到[2,1,6,4,5,7]，它比当前的小。很明显，我需要把5换成更小的数字，但换的是哪一个呢？如果我用5换2，我得到[5,1,6,4,7,2]，这个增量太大了。我需要将5换成"较低的数字"，以保持尽可能小的增量。这将使我们找到小于5的第一个(最低)数字(从右到左)。在这种情况下，我需要将5替换为4并得到[2,1,6,5,7,4]。这样一来，我就可以让"掉期"的影响变得很小。现在决定了前缀[2,1,6,5。没有更小的前缀了。我们需要处理后缀7,4]。显然，如果我们对后缀进行排序并使其4,7]，那么我们就完成了。

在我们的例子中，有两点不同： 1.我们需要交换最后一个1，因为您不能通过将a 0与它之前的任何数字交换来使排列更大。 2.我们始终可以使用代码中所示的快捷方式对后缀进行排序。我将把它留给您：)