- Leads to improved understanding (by comparing and contrasting) the algo & code for generating permutations. We will talk about that in another blog article.
- We get to learn the use of a construct in Python (at least one that I hadn't known or used before).
- Personal amusement.

- The reader is invited to try out the trinket code snippet placed above. Click Run to execute the code. Play with a couple of more inputs. Have a cursory glance at the code, see which parts are appearing unfamiliar, etc. Then, forget it :-).
- Now start with the Analysis section below. This section will at first reading appear onerous - since I show the reader how to design invariants in order to reason about the program. This is a thought process that pays enormous dividends after it has been internalized - though at first look, it might appear pedantic and daunting.
- By the end, we would have reconstructed the code above (more or less). We will also try to modularize some of the code above that translates our understanding of the problem directly.
- Finally, we will list out the main take-aways from this exercise.

Also observe that given the set of $n$ characters input as an

Sample lexicographical ordering (for $n=5$, $r = 3$): $012 < 013< 014 < 023 < 024 < 034 < 123 < 124 < 134 < 234$.

- There are
*two*essential parameters in the problem, $n$ and $r$. If the set of all indices is $\{0, 1, \cdots, n-1\}$, then we are picking up $r$ subsets of this*universe*. (Why subsets? Because these are combinations. If we end up selecting the subset $\{1, 3, 4\}$ that corresponds to precisely one combination - and vice versa). So we can think of keeping two variables: $\mathrm{universe} = \mathrm{range}(n)$ or $\mathrm{indices} = \mathrm{range}(r)$. - The dilemma here is: we will need an array of $r$ elements, but those elements can be anywhere in $\mathrm{range}(n)$. How do we manage this?
- The easiest way of setting aside storage for $r$ elements is to set $\mathrm{indices} = \mathrm{range}(r)$.
Here, we are slightly stretching our mind. Let this be the
*initialization*of the $\mathrm{indices}$ array! **Bottomline**: Since the algorithm need only output the indices of the $r$-subsets, we will not need the $\mathrm{universe}$ as an explicit set (of course we will need the value of $n$). Hence, we keep $\mathrm{indices} = \mathrm{range}(r)$ (Look at line 8 of the code above).

Looking at the sequence of $5 \choose 3$ combinations above (for the combinations for $n = 5$ and $r = 3$), we notice that the changes seem to be starting at the

- One way is to use Python list comprehensions, given input array $A$, and if we wanted to increase each
array element by an amount $t$ to generate array $B$:
B = [x+t for x in A]

- Or, use numpy arrays (see this
SO link):
import numpy A1=numpy.array(A) B=A1+t

This makes sense since we are searching for

In order to introduce Invariant 2, we will introduce some nomenclature. Let us try to understand how the transition is made from one combination to the next. Specifically, given a combination (say, $124$), we will attempt to find out where the next change should occur. As mentioned above, we will have to look at the array in the

This is an easy corollary of the monotonicity enforced by Invariant 1 (why?). This will pave the way for our final idea, that will actually give us the solution.

To implement the main idea, we will write code for the following functionality: given an input array $\mathrm{indices}$, (and $n$, $r$), return the (unsaturated) index into the array that will be changed next. What is

The correct behavior we desire is that we need to search the entire array, break-ing (or return-ing) only when we find a

```
def find_index_to_change(indices,n, r):
for i in reversed(range(r)):
if indices[i] < (i + n - r):
return i
```

In this corner case, we would like to output a default value (say $-1$).

So how do we implement this desired behavior, i.e. of returning a default (say, $-1$) if we are unable to find any
unsaturated index? **Answer:** We would need to add an $\mathrm{else}$ clause to the $\mathrm{for}$ loop above.

Wait a minute, wha...t? An else-clause paired with the for loop? Yes, such a construct indeed exists - and it finds use in precisely such scenarios as this: if we have zipped through a for-loop without break-ing or return-ing from it, then the else conditional is reached.

This gives us the correct implementation of find_index_to_change:```
def find_index_to_change(indices,n, r):
for i in reversed(range(r)):
if indices[i] < (i + n - r):
return i
else:
return -1
```

See this SO link for more discussion on this interesting and useful construct!

The work that needs to be done is actually simple. If $i$ is the index that initiates the change, the actual change consists of

```
def change_indices(indices,i):
r = len(indices)
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] +1
return indices
```

- Initialize indices.
- Repeatedly call find_index_to_change (till it does not return -1) to get index i.
- Use the function change_indices to change the indices array.

I also leave it to the reader to check out the section on *permutations* on the
itertools website, and conduct a similar analysis for
that code.

The main take-aways are

- It helps to think invariants when formulating algorithmic solutions.
- Modular thinking helps. Give meaningful names to the different modules, so that code becomes easier to read.

Created 19 March 2017.