Algoritmo più veloce per lo spostamento del cerchio: array di dimensioni N per la posizione M

Question

Qual è l'algoritmo più veloce per l'array di spostamento del cerchio per le posizioni M?
Per esempio, [3 4 5 2 3 1 4] spostamento M = 2 posizioni dovrebbero essere [1 4 3 4 5 2 3].

Molte grazie.

Answer 1

Se volete O (n) e nessun utilizzo della memoria supplementare (dal array è stato specificato), utilizzare l'algoritmo dal libro di Jon Bentley, "Programmazione Perle 2nd Edition". Si scambia tutti gli elementi per due volte. Non il più velocemente utilizzando le liste collegate, ma usa meno memoria ed è concettualmente semplice.

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) inverte l'ordine degli elementi da startIndex a endIndex, compreso.

Answer 2

E 'solo una questione di rappresentanza. Mantenere l'indice corrente come variabile intera e quando si attraversa la matrice a uso modulo sapere quando avvolgere. Spostamento viene quindi solo cambiando il valore dell'indice corrente, avvolgendolo intorno alla dimensione della matrice. Si tratta naturalmente di O (1).

Ad esempio:

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

Answer 3

Soluzione ottimale

Domanda richiesta più velocemente.Invertire tre volte è più semplice ma sposta ogni elemento esattamente due volte, richiede tempo O(N) e spazio O(1).È possibile effettuare lo spostamento circolare di un array spostando ciascun elemento esattamente una volta anche nel tempo O(N) e nello spazio O(1).

Idea

Possiamo spostare il cerchio in una serie di lunghezze N=9 di M=1 con un ciclo:

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

E se N=9, M=3 possiamo circoscrivere lo spostamento con tre cicli:

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;

Nota che ogni elemento viene letto e scritto una volta.

Diagramma dello spostamento N=9, M=3

Il primo ciclo è mostrato in nero con numeri che indicano l'ordine delle operazioni.Il secondo e il terzo ciclo sono mostrati in grigio.

Il numero di cicli richiesti è il Massimo comun divisore (GCD) di N E M.Se il MCD è 3, iniziamo un ciclo a ciascuno di {0,1,2}.Il calcolo del GCD è veloce con Algoritmo GCD binario.

Codice di esempio:

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

Codice in C per qualsiasi tipo di array:

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

Modificare:Questo algoritmo potrebbe anche avere prestazioni migliori rispetto all'inversione dell'array (when N è grande e M è piccolo) a causa della località della cache, poiché stiamo eseguendo il loop dell'array a piccoli passi.

Nota finale: se il tuo array è piccolo, il triplo inverso è semplice.Se si dispone di un array di grandi dimensioni, vale la pena calcolare il GCD per ridurre il numero di mosse di un fattore 2.Rif: http://www.geeksforgeeks.org/array-rotation/

Answer 4

Imposta su con i puntatori, e ci vuole pochissimo tempo. Ogni punti elemento al successivo, e "l'ultimo" (non c'è scorso, dopo tutto, si diceva che era circolare) punti al primo. Un puntatore su "Start" (primo elemento), e forse una lunghezza, e hai il tuo array. Ora, per fare il vostro turno, basta camminare il puntatore di partenza lungo il cerchio.

Richiedi un buon algoritmo, e si ottiene idee sensate. Chiedete per più veloce , e si ottiene idee strane!

Answer 5

Questo algoritmo viene eseguito in O (n) e O (1) spazio. L'idea è quella di tracciare ciascun gruppo ciclico nel passaggio (numerate da variabile nextGroup).

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

Answer 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

Questo codice funziona bene anche su turni negativo k

Answer 7

funzione C arrayShiftRight. Se spostamento è negativo matrice turni funzione sinistro. È ottimizzato per meno uso di memoria. tempo di esecuzione è 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];
        }
    }
}

Answer 8

Una soluzione molto semplice. Questo è un modo molto veloce, qui uso un array di temperatura con la stessa dimensione o originale e collegare alla variabile originale alla fine. Questo metodo uso O (n) la complessità temporale e O (n) spazio complessità ed è molto semplice da implementare.

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;

Answer 9

A seconda della struttura dei dati che si utilizza, è possibile farlo in O (1). Penso che il modo più veloce è quello di tenere la matrice nella forma di una lista collegata, e hanno una tabella di hash che può tradurre tra "indice" nella matrice di "puntatore" alla voce. In questo modo si possono trovare le teste e le code rilevanti in O (1), e fare la riconnessione in O (1) (e aggiornare la tabella di hash dopo il passaggio in O (1)). Questo, naturalmente, sarebbe una soluzione molto "disordinato", ma se tutto quello che ti interessa è la velocità dello spostamento, che farà (a scapito di più l'inserimento e la ricerca nella matrice, ma sarà ancora O ( 1))

Se si dispone i dati in un array puro, non credo che si può evitare di O (n).

Codifica-saggio, dipende da quale lingua si sta utilizzando.

In Python, ad esempio, si potrebbe "fetta" di esso (assume n è la dimensione turno):

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

(so che di ricerca hash è in teoria non O (1), ma noi siamo qui pratico e non teorico, almeno lo spero ...)

Answer 10

Questo dovrebbe funzionare per spostare un circolarmente Arry: Ingresso: {1, 2, 3, 5, 6, 7, 8}; Valore di uscita presente nella matrice dopo le 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];
            }            
        }
    }

Answer 11

Ecco un semplice ed efficace in generale posto funzione ruotare in C ++, meno di 10 righe.

, che è tratto da mia risposta su un'altra domanda. Come ruotare un 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';
}

Answer 12

Mantenere due indici alla matrice, un indice comincia dall'inizio della matrice per la fine della matrice. Un altro indice inizia dalla posizione Mth dall'ultima e passanti attraverso gli ultimi elementi M qualsiasi numero di volte. Prende O (n) in ogni momento. Nessuno spazio aggiuntivo richiesto.

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;

 }
}

Answer 13

Vedere questo, se siete interessati a un'implementazione Java:

Perle di programmazione: circolare sinistra / Destra Maiusc Operazione

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

Answer 15

Rubino esempio:

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

Answer 16

In teoria, il più veloce è un ciclo come questo:

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 pratica, si dovrebbe profilo e vedere.

Answer 17

Ecco un nother uno (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()] );
}

Naturalmente non è così elegante come la famosa soluzione di reverse-tre volte, ma a seconda della macchina che può essere Analogamente veloce.

Answer 18

circleArray ha degli errori e non funziona in tutti i casi!

Il ciclo deve continuare while i1 < i2 NON 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;
    }
}

Answer 19

Un mio amico, mentre scherzando mi ha chiesto come spostare un array, mi si avvicinò con questa soluzione (vedi link Ideone), la tua ora che ho visto, qualcuno sembra un po 'esoterico.

qui .

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

Answer 20

Questo metodo farà questo lavoro:

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

Answer 21

Simile a @IsaacTurner e non che elegante grazie alla copia inutile, ma l'attuazione è piuttosto breve.

L'idea - elemento di swap A su indice 0 con l'elemento B che si trova sulla destinazione di A. Ora B è prima. Scambiarlo con l'elemento C che si trova sulla destinazione di B. Continuare fino a quando la destinazione non è a 0.

Se il massimo comun divisore non è 1, allora non si è ancora finito -. È necessario continuare lo scambio, ma ora con indice 1 alla vostra partenza e punto finale

Continua fino a quando la posizione di partenza non è il MCD.

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

Answer 22

Ecco la mia soluzione in Java, che mi ha dato il 100% Task Score e il 100% Correttezza a 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];
    }
}

Si noti che nonostante vedendo due anelli for, l'iterazione sull'intero array viene fatto solo una volta.

Answer 23

Swift 4 versione per spostare matrice sinistra.

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
}

Ad esempio, se il vettore di ingresso è a = [1, 2, 3, 4, 5], e offset shift sinistro è d = 4, quindi risultato sarà [5, 1, 2, 3, 4]