Moving memory

[WhiteCube]

pseudocode
M is an integer constant > 0
S is an integer constant >= 0
d = array of M zeroes
d[0] = 1
i = S % M
WHILE i != 0
   d[i] = 1
   i = (i + S) % M

conjecture: when the program ends, the ones are regularly (equal distance) spaced around array d

I'm having trouble proving this. I suspect I'm overlooking (senior moment) something obvious.

Its important because if true, I can rotate any array any distance with only M (size of array) assignments, and no extra memory.

 

[WhiteCube]

I was reading a program that had this in it:

The author was modifying an array, inserting C between A and B

<--A--> <--B--> <----C---->

to

<--A--> <----C----> <--B-->

by moving all the values of B, one position to the right, moving the first value of C into the open gap, then repeating.

The constraint was they couldn't use extra memory.

There had to be a better way than that. (it was part of a sort algorithm, so speed was kind of important)

 

[WhiteCube]

I'm 99% sure the conjecture is true. I have an informal proof which convinces myself, but I'd never post it in public.

rotate(d,beg,end,shf)
/* rotate inside array d, from beg to end, shf positions left */
m = (end - beg) + 1
ini = 0
src = ini
LOOP m TIMES
  des = src
  src = (src + shf) % m
  IF src = ini
    ini += 1 /* 99% sure */
    src = ini
  ELSE
    SWAP d[beg + des], d[beg + src]

 

[WhiteCube]

I've just read that this is a common programming excercise.

There is a simpler solution that uses 3 reverses, on leetcode.

I may have reinvented the wheel, but at least mine is hard to read.