如何求N个组合R中的第k项 [英] How to get the kth term in N Combination R

问题描述

如何在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.我们始终可以使用代码中所示的快捷方式对后缀进行排序。我将把它留给您：)

这篇关于如何求N个组合R中的第k项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！