Fastest algorithm for circle shift N sized array f

问题:

What is the fastest algorithm for circle shifting array for M positions?
For example, [3 4 5 2 3 1 4] shift M = 2 positions should be [1 4 3 4 5 2 3].

Thanks a lot.

回答1:

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.

回答2:

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;
}

回答3:

Optimal solution

Question asked for fastest. Reversing three times is simplest but moves every element exactly twice, takes O(N) time and O(1) space. It is possible to circle shift an array moving each element exactly once also in O(N) time and O(1) space.

Idea

We can circle shift an array of length N=9 by M=1 with one cycle:

tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;

And if N=9, M=3 we can circle shift with three cycles:

1. tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
2. tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
3. tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;

Note each element is read once and written once.

Diagram of shifting N=9, M=3

The first cycle is show in black with numbers indicating the order of operations. The second and third cycles are shown in grey.

The number of cycles required is the Greatest Common Divisor (GCD) of N and M. If the GCD is 3, we start a cycle at each of {0,1,2}. Calculating the GCD is fast with the binary GCD algorithm.

Example code:

// n is length(arr)
// shift is how many place to cycle shift left
void cycle_shift_left(int arr[], int n, int shift) {
  int i, j, k, tmp;
  if(n <= 1 || shift == 0) return;
  shift = shift % n; // make sure shift isn't >n
  int gcd = calc_GCD(n, shift);

  for(i = 0; i < gcd; i++) {
    // start cycle at i
    tmp = arr[i];
    for(j = i; 1; j = k) {
      k = j+shift;
      if(k >= n) k -= n; // wrap around if we go outside array
      if(k == i) break; // end of cycle
      arr[j] = arr[k];
    }
    arr[j] = tmp;
  }
}

Code in C for any array type:

// circle shift an array left (towards index zero)
// - ptr    array to shift
// - n      number of elements
// - es     size of elements in bytes
// - shift  number of places to shift left
void array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift)
{
  char *ptr = (char*)_ptr;
  if(n <= 1 || !shift) return; // cannot mod by zero
  shift = shift % n; // shift cannot be greater than n

  // Using GCD
  size_t i, j, k, gcd = calc_GCD(n, shift);
  char tmp[es];

  // i is initial starting position
  // Copy from k -> j, stop if k == i, since arr[i] already overwritten
  for(i = 0; i < gcd; i++) {
    memcpy(tmp, ptr+es*i, es); // tmp = arr[i]
    for(j = i; 1; j = k) {
      k = j+shift;
      if(k >= n) k -= n;
      if(k == i) break;
      memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k];
    }
    memcpy(ptr+es*j, tmp, es); // arr[j] = tmp;
  }
}

// cycle right shifts away from zero
void array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift)
{
  if(!n || !shift) return; // cannot mod by zero
  shift = shift % n; // shift cannot be greater than n
  // cycle right by `s` is equivalent to cycle left by `n - s`
  array_cycle_left(_ptr, n, es, n - shift);
}

// Get Greatest Common Divisor using binary GCD algorithm
// http://en.wikipedia.org/wiki/Binary_GCD_algorithm
unsigned int calc_GCD(unsigned int a, unsigned int b)
{
  unsigned int shift, tmp;

  if(a == 0) return b;
  if(b == 0) return a;

  // Find power of two divisor
  for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; }

  // Remove remaining factors of two from a - they are not common
  while((a & 1) == 0) a >>= 1;

  do
  {
    // Remove remaining factors of two from b - they are not common
    while((b & 1) == 0) b >>= 1;

    if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b
    b = b - a;
  }
  while(b != 0);

  return a << shift;
}

Edit: This algorithm may also have better performance vs array reversal (when N is large and M is small) due to cache locality, since we are looping over the array in small steps.

Final note: if your array is small, triple reverse is simple. If you have a large array, it is worth the overhead of working out the GCD to reduce the number of moves by a factor of 2. Ref: http://www.geeksforgeeks.org/array-rotation/

回答4:

Set it up with pointers, and it takes almost no time. Each element points to the next, and the "last" (there is no last; after all, you said it was circular) points to the first. One pointer to the "start" (first element), and maybe a length, and you have your array. Now, to do your shift, you just walk your start pointer along the circle.

Ask for a good algorithm, and you get sensible ideas. Ask for fastest, and you get weird ideas!

回答5:

This algorithm runs in O(n) time and O(1) space. The idea is to trace each cyclic group in the shift (numbered by nextGroup variable).

var shiftLeft = function(list, m) {
    var from = 0;
    var val = list[from];
    var nextGroup = 1;
    for(var i = 0; i < list.length; i++) {
        var to = ((from - m) + list.length) % list.length;
        if(to == from)
            break;

        var temp = list[to];
        list[to] = val;
        from = to;
        val = temp;

        if(from < nextGroup) {
            from = nextGroup++;
            val = list[from];
        }
    }
    return list;
}

回答6:

def shift(nelements, k):       
    result = []
    length = len(nelements)
    start = (length - k) % length
    for i in range(length):
        result.append(nelements[(start + i) % length])
    return result

This code works well even on negative shift k

回答7:

C arrayShiftRight function. If shift is negative the function shifts array left. It is optimized for less memory usage. Running time is O(n).

void arrayShiftRight(int array[], int size, int shift) {
    int len;

    //cut extra shift
    shift %= size;

    //if shift is less then 0 - redirect shifting left
    if ( shift < 0 ) {
        shift += size;
    }

    len = size - shift;

    //choosing the algorithm which needs less memory
    if ( shift < len ) {
        //creating temporary array
        int tmpArray[shift];

        //filling tmp array
        for ( int i = 0, j = len; i < shift; i++, j++ ) {
            tmpArray[i] = array[j];
        }

        //shifting array
        for ( int i = size - 1, j = i - shift; j >= 0; i--, j-- ) {
            array[i] = array[j];
        }

        //inserting lost values from tmp array
        for ( int i = 0; i < shift; i++ ) {
            array[i] = tmpArray[i];
        }
    } else {
        //creating temporary array
        int tmpArray[len];

        //filling tmp array
        for ( int i = 0; i < len; i++ ) {
            tmpArray[i] = array[i];
        }

        //shifting array
        for ( int i = 0, j = len; j < size; i++, j++ ) {
            array[i] = array[j];
        }

        //inserting lost values from tmp array
        for ( int i = shift, j = 0; i < size; i++, j++ ) {
            array[i] = tmpArray[j];
        }
    }
}

回答8:

A very simple solution. This is a very fast way, here I use a temp array with the same size or original and attach to the original variable at the end. This method use O(n) temporal complexity and O(n) space complexity and it is very simple to implement.

int[] a  = {1,2,3,4,5,6};
    int k = 2;
    int[] queries = {2,3};

    int[] temp = new int[a.length];
    for (int i = 0; i<a.length; i++)
        temp[(i+k)%a.length] = a[i];

    a = temp;

回答9:

Depending on the data structure you use, you can do it in O(1). I think the fastest way is to hold the array in the form of a linked list, and have a hash table that can translate between "index" in the array to "pointer" to the entry. This way you can find the relevant heads and tails in O(1), and do the reconnection in O(1) (and update the hash table after the switch in O(1)). This of course would be a very "messy" solution, but if all you're interested in is the speed of the shift, that will do (on the expense of longer insertion and lookup in the array, but it will still remain O(1))

If you have the data in a pure array, I don't think you can avoid O(n).

Coding-wise, it depends on what language you are using.

In Python for example, you could "slice" it (assume n is the shift size):

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

(I know that hash lookup is in theory not O(1) but we're practical here and not theoretical, at least I hope so...)

回答10:

This should work to shift an arry circularly: Input : { 1, 2, 3, 5, 6, 7, 8 }; Output value present in array after the forloops : {8,7,1,2,3,5,6,8,7}

 class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 1, 2, 3, 5, 6, 7, 8 };
            int index = 2;
            int[] tempArray = new int[array.Length];
            array.CopyTo(tempArray, 0);

            for (int i = 0; i < array.Length - index; i++)
            {
                array[index + i] = tempArray[i];
            }

            for (int i = 0; i < index; i++)
            {
                array[i] = tempArray[array.Length -1 - i];
            }            
        }
    }

回答11:

Here is a simple and efficient general in place rotate function in C++, less than 10 lines.

which is excerpted from my answer on another question. How to rotate an array?

#include <iostream>
#include <vector>

// same logic with STL implementation, but simpler, since no return value needed.
template <typename Iterator>
void rotate_by_gcd_like_swap(Iterator first, Iterator mid, Iterator last) {
    if (first == mid) return;
    Iterator old = mid;
    for (; mid != last;) {
        std::iter_swap(first, mid);
        ++first, ++mid;
        if (first == old) old = mid; // left half exhausted
        else if (mid == last) mid = old;
    }
}

int main() {
    using std::cout;
    std::vector<int> v {0,1,2,3,4,5,6,7,8,9};
    cout << "before rotate: ";
    for (auto x: v) cout << x << ' '; cout << '\n';
    int k = 7;
    rotate_by_gcd_like_swap(v.begin(), v.begin() + k, v.end());
    cout << " after rotate: ";
    for (auto x: v) cout << x << ' '; cout << '\n';
    cout << "sz = " << v.size() << ", k = " << k << '\n';
}

回答12:

Keep two indexes to the array, one index starts from beginning of the array to the end of array. Another index starts from the Mth position from last and loops through the last M elements any number of times. Takes O(n) at all times. No extra space required.

circleArray(Elements,M){
 int size=size-of(Elements);

 //first index
 int i1=0;

 assert(size>M)

 //second index starting from mth position from the last
 int i2=size-M;

 //until first index reaches the end
 while(i1<size-1){

  //swap the elements of the array pointed by both indexes
  swap(i1,i2,Elements);

  //increment first pointer by 1
  i1++;

  //increment second pointer. if it goes out of array, come back to
  //mth position from the last
  if(++i2==size) i2=size-M;

 }
}

回答13:

See this if you are interested in a Java implementation:

Programming Pearls: Circular Left/Right Shift Operation

回答14:

static int [] shift(int arr[], int index, int k, int rem)
{
    if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length)
    {
        return arr;
    }

    int temp = arr[index];

    arr = shift(arr, (index+k) % arr.length, k, rem - 1);

    arr[(index+k) % arr.length] = temp;

    return arr;
}

回答15:

Ruby example:

def move_cyclic2 array, move_cnt
  move_cnt = array.length - move_cnt % array.length 
  if !(move_cnt == 0 || move_cnt == array.length)            
    array.replace( array[move_cnt..-1] + array[0...move_cnt] )  
  end   
end

回答16:

In theory, the fastest one is a loop like this:

if (begin != middle && middle != end)
{
    for (i = middle; ; )
    {
        swap(arr[begin++], arr[i++]);
        if (begin == middle && i == end) { break; }
        if (begin == middle) { middle = i; }
        else if (i == end) { i = middle; }
    }
}

In practice, you should profile it and see.

回答17:

Here is a nother one (C++):

void shift_vec(vector<int>& v, size_t a)
{
    size_t max_s = v.size() / a;
    for( size_t s = 1; s < max_s; ++s )
        for( size_t i = 0; i < a; ++i )
            swap( v[i], v[s*a+i] );
    for( size_t i = 0; i < a; ++i )
        swap( v[i], v[(max_s*a+i) % v.size()] );
}

Of course it is not nearly as elegant as the famous reverse-three-times solution, but depending on the machine it can be similary fast.

回答18:

circleArray has some errors and is not working in all cases!

The loop must continue while i1 < i2 NOT i1 < last - 1.

void Shift(int* _array, int _size, int _moves)
{
    _moves = _size - _moves;
    int i2 = _moves;
         int i1 = -1;
         while(++i1 < i2)
    {
        int tmp = _array[i2];
        _array[i2] = _array[i1];
        _array[i1] = tmp;
        if(++i2 == _size) i2 = _moves;
    }
}

回答19:

A friend of mine while joking asked me how to shift an array, I came up with this solutions (see ideone link), now I've seen yours, someone seems a bit esoteric.

Take a look here.

#include <iostream>

#include <assert.h>

#include <cstring>

using namespace std;

struct VeryElaboratedDataType
{
    int a;
    int b;
};

namespace amsoft
{
    namespace inutils
    {
        enum EShiftDirection
        {
            Left,
            Right
        };
template 
<typename T,size_t len>
void infernalShift(T infernalArray[],int positions,EShiftDirection direction = EShiftDirection::Right)
{
    //assert the dudes
    assert(len > 0 && "what dude?");
    assert(positions >= 0 && "what dude?");

    if(positions > 0)
    {
    ++positions;
    //let's make it fit the range
    positions %= len;

    //if y want to live as a forcio, i'l get y change direction by force
    if(!direction)
    {
        positions = len - positions;
    }

    // here I prepare a fine block of raw memory... allocate once per thread
    static unsigned char WORK_BUFFER[len * sizeof(T)];
    // std::memset (WORK_BUFFER,0,len * sizeof(T));
    // clean or not clean?, well
    // Hamlet is a prince, a prince does not clean

    //copy the first chunk of data to the 0 position
    std::memcpy(WORK_BUFFER,reinterpret_cast<unsigned char *>(infernalArray) + (positions)*sizeof(T),(len - positions)*sizeof(T));
    //copy the second chunk of data to the len - positions position
    std::memcpy(WORK_BUFFER+(len - positions)*sizeof(T),reinterpret_cast<unsigned char *>(infernalArray),positions * sizeof(T));

    //now bulk copy back to original one
    std::memcpy(reinterpret_cast<unsigned char *>(infernalArray),WORK_BUFFER,len * sizeof(T));

    }

}
template 
<typename T>
void printArray(T infernalArrayPrintable[],int len)
{
        for(int i=0;i<len;i++)
    {
        std::cout << infernalArrayPrintable[i] << " ";
    }
    std::cout << std::endl;

}
template 
<>
void printArray(VeryElaboratedDataType infernalArrayPrintable[],int len)
{
        for(int i=0;i<len;i++)
    {
        std::cout << infernalArrayPrintable[i].a << "," << infernalArrayPrintable[i].b << " ";
    }
    std::cout << std::endl;

}
}
}




int main() {
    // your code goes here
    int myInfernalArray[] = {1,2,3,4,5,6,7,8,9};

    VeryElaboratedDataType myInfernalArrayV[] = {{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{8,8},{9,9}};
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
    amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4);
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
    amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4,amsoft::inutils::EShiftDirection::Left);
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
    amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,10);
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));


    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
    amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4);
    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
    amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4,amsoft::inutils::EShiftDirection::Left);
    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
    amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,10);
    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));

    return 0;
}

回答20:

This method will do this work :

public static int[] solution1(int[] A, int K) {
    int temp[] = new int[A.length];

    int count = 0;

    int orignalItration = (K < A.length) ? K :(K%A.length); 


    for (int i = orignalItration; i < A.length; i++) {
        temp[i] = A[count++];
    }
    for (int i = 0; i < orignalItration; i++) {
        temp[i] = A[count++];
    }

    return temp;
}

回答21:

Similar to @IsaacTurner and not that elegant due to unnecessary copying, but implementation is quite short.

The idea - swap element A on index 0 with the element B which sits on destination of A. Now B is first. Swap it with the element C which sits on destination of B. Continue until the destination is not at 0.

If the greatest common divisor is not 1 then you're not finished yet - you need to continue swapping, but now using index 1 at your starting and end point.

Continue until your starting position is not the gcd.

int gcd(int a, int b) => b == 0 ? a : gcd(b, a % b);

public int[] solution(int[] A, int K)
{
    for (var i = 0; i < gcd(A.Length, K); i++)
    {
        for (var j = i; j < A.Length - 1; j++)
        {
            var destIndex = ((j-i) * K + K + i) % A.Length;
            if (destIndex == i) break;
            var destValue = A[destIndex];
            A[destIndex] = A[i];
            A[i] = destValue;
        }
    }

    return A;
}

回答22:

Here is my solution in Java which got me 100% Task Score and 100% Correctness at Codility:

class Solution {
    public int[] solution(int[] A, int K) {
        // write your code in Java SE 8
        if (A.length > 0)
        {
            int[] arr = new int[A.length];
            if (K > A.length)
                K = K % A.length;

            for (int i=0; i<A.length-K; i++)
                arr[i+K] = A[i];

            for (int j=A.length-K; j<A.length; j++)
                arr[j-(A.length-K)] = A[j];

            return arr;
        }
        else
            return new int[0];
    }
}

Note that despite seeing two for loops, the iteration on the entire array is only done once.

回答23:

Swift 4 version for shifting array left.

func rotLeft(a: [Int], d: Int) -> [Int] {

   var result = a
   func reverse(start: Int, end: Int) {
      var start = start
      var end = end
      while start < end {
         result.swapAt(start, end)
         start += 1
         end -= 1
      }
   }

   let lenght = a.count
   reverse(start: 0, end: lenght - 1)
   reverse(start: lenght - d, end: lenght - 1)
   reverse(start: 0, end: lenght - d - 1)
   return result
}

For example, if input array is a = [1, 2, 3, 4, 5], and left shift offset is d = 4, then result will be [5, 1, 2, 3, 4]