Should we use "pythonic" indexing when teaching about permutations

Question

When teaching abstract algebra for undergrads, I taught them that there is a permutation group $S(A)$ of automorphisms on any set $A$, and then defined the group $S_n$ to be the group of permutations of the set $\{1,\dots, n\}.$ Later in the semester I regretted it: when writing down cycles (and using cycle notation in general), you want the indices to be modulo some integer: so I wrote cycles of length $n$ as $(x_0, \dots, x_{n-1}),$ which was confusing.

The "pythonic" philosophy holds that the set $\{0, \dots, n-1\}$ is better behaved than the set $\{1,\dots, n\},$ and from a purely ease of notation perspective I think it would be better to define $S_n$ as permutations of $\{0. \dots, n-1\}$. Another consideration that makes this notation potentially better is that the group $D_n$ embeds naturally in $S_n$ as permutations of angles of the $n$-gon, which are indexed $\big\{0\cdot \frac{2\pi}{n},\dots, (n-1)\cdot \frac{2\pi}{n}\big\}$. On the other hand, this notation feels less intuitive and is less standard, not to mention that the book I'm using (Fraleigh, which has multiple chapters on permutation groups) uses $\{1,\dots, n\}.$

I am teaching the same course again and am debating switching. Have people considered this or tried this in their teaching, and what are the main pros/cons?

Answer 1

In my opinion, it is a serious mistake to think that only one of 1-based or 0-based indexing is the best one, even in the programming world, not to say the mathematics world. Each scenario has its own structure that should guide you to the most natural choice of indexing scheme:

• If you have an initial state, it is natural to start at index $0$. This includes a sequence $x[0..n]$ where $x[k]$ is the state after $k$ steps of some process.

• If you are labelling $n$ objects, it is almost always most convenient to use labels $[1..n]$, unless the labels somehow have more meaning than just labels.

In your case, your underlying set just needs $n$ labels, so $[1..n]$ works just fine. A cycle can indeed be thought of as a length-$n$ sequence modulo rotation, which favours the choice of $(x_0,x_1,\cdots,x_{n-1})$. But I am kind of doubtful that there is any serious inelegance in using $(x_1,x_2,\cdots,x_n)$. If there is some theorem where one indexing seems more natural than the other, simply use that.

There is no such thing as a "more Pythonic indexing scheme". You cannot imagine how many times when coding in Python I cringed because I wanted to say for i in [0..n] but had to use for i in range(n+1) just because ... and wanted to say for i in [1..n] and had to use for i in range(n) and have +1s all over.

Answer 2

I work extensively with $S_n$, and I strongly prefer indexing beginning at $1$. I also program quite a bit, and I wrap permutations in classes that make them start at $1$ as well. Programming is actually something I began first, as a child, yet the $1$-based indexing still seems preferable to me.

Likely the reason is that so many things in mathematics begin at $1$, and shifting everything to begin at $0$ leads to error when the $1$-based indexing is already well established. Computer scientists hardly use groups, the vast majority of them don't even know what they are, and the reason for $0$-based indexing is so that the array index is the address offset. There's really no other reason. Counting generally begins at $1$, it is an oddity of computing that we have them begin at $0$.

$0$ is useful to have be part of $\mathbb{N}$ in my experience, but seeing it in a permutation grates on my nerves, although of course it's perfectly correct if that is the set you choose $S_n$ to act on. If you want to take indices modulo some integer, that's not necessarily a reason to start at $0$. $\{1,\ldots,n\}$ is also a complete set of residues modulo $n$, you've just replaced $0$ with $n$.

The only time I've used $0$-based indexing for permutations is when I needed extremely rapid computation that had to use as little memory as possible, where instead of representing a permutation as an array I represented them by their index in lexicographical order. You can see the code here: https://codereview.stackexchange.com/questions/182610/computing-the-number-of-primitive-sorting-networks-on-n-elements-seeking-tiny