First let's solve the Question(Example 5) :
Q : What will be the Next larger 4-combination of the set $\left \{ 1,2,3,4,5,6 \right \}$ after $\left \{ 1,2,5,6 \right \}$ :
See, the $Meaning$ of $r-combinations$ :
- The $r-combinations$ can be listed using lexicographic order.
- A $r-combination$ is a subset of $r$ elements which are listed in increasing order.
Now, Using this Definition, we can directly(intuitively) find the Next larger 4-combination of the set $\left \{ 1,2,3,4,5,6 \right \}$ after $\left \{ 1,2,5,6 \right \}$ which will be $\left \{ 1,3,4,5 \right \}$ (because of simple Dictionary order and with the added condition of being increasing.)
The First 4-combination will be $\left \{ 1,2,3,4 \right \}$ (as it would be in Dictionary) (NOTE that $\left \{ 1,1,1,1 \right \}$) can't be the first 4-combination in the Dictionary as there is added condition of "Increasing order"..A $4-combination$ is a subset of $4$ elements which are listed in increasing order.)
The next 4-combination will be $\left \{ 1,2,3,5 \right \}$ as in dictionary.
So, let's list some combinations as they would be present in the 4-combinations dictionary :
1. $\left \{ 1,2,3,4 \right \}$
2. $\left \{ 1,2,3,5 \right \}$
3. $\left \{ 1,2,3,6 \right \}$
Now, the series that begins with $1,2,3$ (in that order) has ended.
4. $\left \{ 1,2,4,5 \right \}$
5. $\left \{ 1,2,4,6 \right \}$
Now, the series that begins with $$1,2,4$(in that order) has ended.
6. $\left \{ 1,2,5,6 \right \}$
Now, the series that begins with $1,2,5$(in that order) has ended.
And so on. So, that is the intuitive idea. It tells us what is actually happening here.
Now, You can just easily prove that the Algorithm for finding the Next r-combination which is as follows :
Algorithm $r$ :
[ The next r-combination after $a_1a_2 ··· a_r$ can be obtained in the following way:
First, locate the last element $a_i$ in the sequence such that $a_i \neq n − r + i$. Then, replace $a_i$ with $a_{i + 1}$ and $a_j$ with $a_i + j − i + 1$, for $j = i + 1, i + 2,...,r$ ]
produces the next larger r-combination in lexicographic order.
Hint for Proving :
1. In the above intuitive manual way we were finding the Longest Series which hasn't ended yet and we were increasing the next element(s) following this series --- in r-combination manner. Like In Example $5$, $\left \{ 1,2,5,6 \right \}$ ... Series that begins with $1,2$ has ended. So, the Longest series that hasn't ended yet is ----which begins with $1$. So, We increased its following elements in r-combination manner which gave us $\left \{ 1,3,4,5 \right \}$
Similarly in the Algorithm $r$, Notice the point "locate the last element"
2. In the r-combination, $\left \{ a_1,a_2,.....a_r \right \}$, What is the maximum value that $a_r$ can take??
$a_r$ can take maximum value $n$. Similarly, What is the maximum value that $a_1$ can take??
$a_1$ can take maximum value $n-r+1$ (Because after $a_1$ there are $r-1$ elements which will be in increasing order).
Similarly, What is the maximum value that $a_i$ can take?
Say the maximum value that $a_i$ can take is $x$, so, we can say that $x + (r-i) \leq n$ (Because after $a_i$ there are $r-i$ elements which will be in increasing order and the last element can take at most value $n$).
So, From $x + (r-i) \leq n$, we can say that the Maximum value that $a_i$ can take, is = $n -r +i$
Now, Consider the Algorithm $r$ and make use of Hint 1 and 2....... You will have your Proof (Which Rosen has left for Reader)
