java - 如何获得N组合R中的第k个项

Closed. This question needs to be more focused。它当前不接受答案。
                            
                        
                    
                
            
                    
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？更新问题，使其仅通过editing this post专注于一个问题。
                        
                        2年前关闭。
                    
                
        

如何获得kth中的NCR组合。而不迭代所有可能的结果。例如说我在3C2职位和3相同项目中有2。我知道它是[011]，[101]和[110]。我如何获得例如使用方法的第二项（k = 1）是[101]吗？

约束（R < N k >= 0和k < P其中P = NCR）。


  注意：[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，因为您不能通过将零与前面的任何数字交换来使排列变大。
2.我们总是可以使用代码中所示的快捷方式对后缀进行排序。我会把它留给你:)