我对以下编程问题感到困惑:
给定一个大小为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)
有什么意义?请告诉我你对此的看法。
1条答案
按热度按时间tf7tbtn21#
它只是对代码的一点点优化。
i
循环来自start
至end
. 在下一个递归中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
在比较之前先递增1r
.两种说法都是正确的,结果相同。你喜欢哪一种取决于你的编码风格。最重要的是你可以在必要的时候创建这样的语句。