1
i = start; 
while(i <= end and end - i + 1 >= r - index): 
    data[index] = arr[i]; 
    combinationUtil(arr, data, i + 1, 
                    end, index + 1, r); 
    i += 1;

I'm having a hard time trying to understand why, "end - i + 1 >= r - index" this condition is needed, I've tried running the code, with and without, it produced the same output, I want to know what is the edge case that causes this condition to return False.

The full code is available here.

RocketBug
  • 43
  • 4
  • I'm not sure if you're trying to understand this (incomplete) snippet or to solve the problem. If it's the latter: https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list – gilad Jan 05 '20 at 15:38
  • I'm trying to understand this snippet, the complete code is provided in the link. – RocketBug Jan 05 '20 at 15:53

1 Answers1

1

Try to group the variables into pieces that are easier to understand e.g.

int values_left_to_print = r - index; // (size of combination to be printed) - (current index into data)
int values_left_in_array = end - i + 1; // number of values left until the end of given arr

Now we can interpret it like this:

for (int i = start; i <= end && (values_left_in_array >= values_left_to_print); i++)  
{

so if i is near the end of the given array and there are not enough values left to print a full combination, then the loop (and function) will stop. Let's look at an example:

Given

arr = {1,2,3,4}
n = 4; // size of arr
r = 3; // size of combination

The top level function will start to form a combination with 1 and then with 2 resulting in (1,2,3), (1,2,4), (1,3,4)

It will not try 3 and 4, because (values_left_in_array < values_left_to_print).

If the condition was not there, then the function would try 3 and 4, but the values in the sequence only ever increase in index from left-to-right in the given array, so the combination will end because i will reach end before being able to find 3 values.

Community
  • 1
  • 1
Kyy13
  • 315
  • 1
  • 9