关于组合问题解决方案代码中循环条件的混淆

bqf10yzr  于 2021-06-30  发布在  Java
关注(0)|答案(1)|浏览(397)

我对以下编程问题感到困惑:
给定一个大小为n的数组,生成并打印数组中r元素的所有可能组合。
此问题的解决方案之一如下:

/* arr[]  ---> Input Array 
    data[] ---> Temporary array to store current combination 
    start & end ---> Staring and Ending indexes in arr[] 
    index  ---> Current index in data[] 
    r ---> Size of a combination to be printed */
    static void combinationUtil(int arr[], int data[], int start, 
                                int end, int index, int r) 
    { 
        // Current combination is ready to be printed, print it 
        if (index == r) 
        { 
            for (int j=0; j<r; j++) 
                System.out.print(data[j]+" "); 
            System.out.println(""); 
            return; 
        } 

        // replace index with all possible elements. The condition 
        // "end-i+1 >= r-index" makes sure that including one element 
        // at index will make a combination with remaining elements 
        // at remaining positions 
        for (int i=start; i<=end && end-i+1 >= r-index; i++) 
        { 
            data[index] = arr[i]; 
            combinationUtil(arr, data, i+1, end, index+1, r); 
        } 
    } 

    // The main function that prints all combinations of size r 
    // in arr[] of size n. This function mainly uses combinationUtil() 
    static void printCombination(int arr[], int n, int r) 
    { 
        // A temporary array to store all combination one by one 
        int data[]=new int[r]; 

        // Print all combination using temprary array 'data[]' 
        combinationUtil(arr, data, 0, n-1, 0, r); 
    }

完整的代码可以在这里找到。
我对这种情况感到困惑 end-i+1 >= r-index 在函数中 combinationUtil 我很难理解它之前的评论:

// replace index with all possible elements. The condition 
    // "end-i+1 >= r-index" makes sure that including one element 
    // at index will make a combination with remaining elements 
    // at remaining positions 
    for (int i=start; i<=end && end-i+1 >= r-index; i++) 
            { 
                data[index] = arr[i]; 
                combinationUtil(arr, data, i+1, end, index+1, r); 
            }

我猜这个表达 r-index 是为了检查r中有多少职位已经被填补(何时 index 是0, r 职位仍在等待被占用,何时被占用 index 是1, r-1 等等)。我不知道该怎么办 end-i+1 但确实如此。我之前认为它是用来表示程序通过计数器/变量在输入数组中的距离 i . 换言之,它希望表示输入数组中还有多少项仍保留在要使用的数组中。然而,这个想法对我来说已经没有意义了。
请解释一下什么 end-i+1 >= r-index 在这个问题的背景下。
编辑1:
我仍然觉得变量的使用令人困惑。 r 是项和的总数 index 对应于数组索引,因此最多比总数少1。把它们相互减去似乎很奇怪。
编辑2:
这个表达式不是吗 end-i >= r-(index+1) 有什么意义?请告诉我你对此的看法。

tf7tbtn2

tf7tbtn21#

它只是对代码的一点点优化。 i 循环来自 startend . 在下一个递归中 start 是最后一个 i + 1 最后一次递归。所以元素被添加到 data 按原来的顺序。 end - i 指示在当前元素之后仍可以使用的元素数 i . end - i + 1 如果包含当前元素,则可以使用多少元素。 r - index - 1 指示仍必须使用多少元素(因为 index 从零开始)。如果回路走得太远 data 无法填补,没有前进的意义。所以这个优化打破了循环和回溯。
现在可以用 end - i + 1 <= r - index - 1 或者 end - i + 1 < r - index . 换句话说 end - i + 1 < r - index 是真的,没有可能的组合。所以当它的否定为真时,循环不应该被打断 end - i + 1 >= r - index .
编辑:
我想 end - i + 1 >= r - index 比…更清楚 end - i >= r - (index + 1) . 在上面是有条件的 r == index 所以使用它也是有意义的 r - index 在下面。 end - i + 1 就像“可以使用多少元素”和 r - index 就像“必须使用多少元素”。如果我们有足够的元素,那么我们可以继续。
end - i >= r - (index + 1) 它是“在此之后可以使用多少元素”和“在此之后必须使用多少元素”。我个人认为这更复杂。这就像跳过当前步骤。我明白为什么人们更喜欢 r - (index + 1) 因为 index 在比较之前先递增1 r .
两种说法都是正确的,结果相同。你喜欢哪一种取决于你的编码风格。最重要的是你可以在必要的时候创建这样的语句。

相关问题