# Circle shifting array for m positions

If you want O(n) time and no extra memory usage (since array was specified), use the algorithm from Jon Bentley's book, "Programming Pearls 2nd Edition". It swaps all the elements twice. Not as fast as using linked lists but uses less memory and is conceptually simple.

shiftArray( theArray, M ):
    size = len( theArray )
    assert( size > M )
    reverseArray( theArray, 0, size - 1 )
      reverseArray( theArray, 0, M - 1 )
    reverseArray( theArray, M, size - 1 )

reverseArray( anArray, startIndex, endIndex ) reverses the order of elements from startIndex to endIndex, inclusive.

==>If only care about the index, not necessary really shift the arｒａｙ：

It's just a matter of representation. Keep the current index as an integer variable and when traversing the array use modulo operator to know when to wrap around. Shifting is then only changing the value of the current index, wrapping it around the size of the array. This is of course O(1).

For example:

int index = 0;
Array a = new Array[SIZE];

get_next_element() {
    index = (index + 1) % SIZE; 
    return a[index];
}

shift(int how_many) {
      index = (index+how_many) % SIZE;
}

==> In Python：

result = original[-n:]+original[:-n]

>>> a = range(10)
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a[:-5]
[0, 1, 2, 3, 4]
>>> a[-5:]
[5, 6, 7, 8, 9]
>>> a[-5:] + a[:-5]
[5, 6, 7, 8, 9, 0, 1, 2, 3, 4]

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position