How to think of string shifts mathematically

Question

I am trying to understand how to think mathematically about the solution to this problem.

The problem statement is:
Come up with an algorithm to left shift a string of length n by s. This problem is pretty common and is also present in "Programming Pearls" book.

So for example the string is abcdefg and s=3 so we want to left shift by 3 to result in the string defgabc.

One of the solutions is
1. store 'a' the first element in a temporary variable t.
2. Now since we need to shift by 3, move 3 elements ahead to 'd' and move it into 'a's location to give dbcdefg; and t=a.
3. Now since d has been moved we can move 3 locations to the right of 'd' and move 'g' into d to give dbcgefg. Now we need to move the element 3 locations to the right and since we will wrap around the element to move is 'c'.
4. Continuing this way we are done when we have made 7 moves and when time comes to read from the first location we read instead from variable t.

Now, if n is divisible by s cleanly then we will have done one round (i.e. read from the first location and yet not moved all n elements. So we start again this time moving element in location 2 to temporary variable t. For eg. if n = 4 and s = 2. However, if n is not cleanly divisible by s then we will have finished the shift in one round. For eg. in the example above with abcdefg and s = 3, n = 7.
7 x 3 = 21 and so after 7 moves we have to read again from location 1 and we are done.

The question is how to prove this mathematically. How to be sure that with a billion numbers and shifting by a a few million numbers we will not somehow be overwriting what we have already shifted and will be done in one round when n is not divisible by s.

What to read to get an intuitive feel for such problems. Any book recommendations? Thank you!

Answer 1

Shifting a string of length $\,n\,$ by $\,s\,$ as you describe is a permutation. Every permutation is composed of disjoint cycles. In the case of a shift all of the cycles have the same length $\,d\,$ which must divide $\,n\,$ and the number of cycles $\,n/d\,$ is the GCD of $\,n\,$ and $\,s.\,$

Implementing a cycle as you describe is done using the steps 1 to 4. The key idea is to use modular arithmetic to keep track of string element positions to move. For example, if we have to shift abcde left by 2 positions then we number the positions i in 01234 and go through them as 02413 by iterating i:=mod(i+2,5). Exactly similar case if we have to shift abcdefg left by 3 positions. Go through the positions as 0362514 by iterating i:=mod(i+3,7).

This generalizes to shifting any amount. All you need is a little bit of integer divisors, modular arithmetic, and permutations. There are lots of information about these topics on the web and elementary books if you want them.