algoritmo más rápido para círculo cambio N array de tamaño para la posición M

Question

¿Cuál es el algoritmo más rápido para el cambio de círculo serie de M posiciones?
Por ejemplo, de cambio [3 4 5 2 3 1 4] M = 2 posiciones deben ser [1 4 3 4 5 2 3].

Muchas gracias.

Answer 1

Si desea un tiempo O (n) y sin el uso de memoria adicional (ya que se especificó matriz), utilizar el algoritmo del libro de Jon Bentley, "Programación Perlas 2ª Edición". Intercambia todos los elementos en dos ocasiones. No es tan rápido como el uso de listas enlazadas, pero utiliza menos memoria y es conceptualmente 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 (unArray, startIndex, endIndex) invierte el orden de los elementos de startIndex a endIndex, inclusive.

Answer 2

Es sólo una cuestión de la representación. Mantener el índice actual como una variable entera y cuando se atraviesa el operador uso de módulo matriz para saber cuándo hay que envolver alrededor. Shifting es entonces solamente cambiando el valor del índice actual, envolviéndola alrededor del tamaño de la matriz. Esto es por supuesto O (1).

Por ejemplo:

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

solución óptima

Pregunta pidió más rápido. Inversión de tres veces es más simple pero mueve cada elemento exactamente dos veces, toma tiempo O (N) y O (1) espacio. Es posible dar la vuelta desplazar una matriz mover cada elemento exactamente una vez también en O (N) tiempo y O (1) espacio.

Idea

Podemos círculo cambiar una matriz de longitud N=9 por M=1 con un ciclo:

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

Y si N=9, M=3 podemos cambiar círculo con tres ciclos:

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;

Tenga en cuenta que cada elemento se lee una vez y escribe una vez.

Diagrama de desplazamiento N=9, M=3

El primer ciclo es espectáculo en negro con números que indican el orden de las operaciones. Los ciclos segundo y tercero se muestran en gris.

El número de ciclos necesarios es el Greatest Common Divisor (GCD) de N y M. Si el MCD es 3, comenzamos un ciclo en cada uno de {0,1,2}. Calcular el MCD es rápido con el algoritmo GCD binaria .

código de ejemplo:

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

Código en C para cualquier tipo de matriz:

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

Editar : Este algoritmo también puede tener un mejor rendimiento vs arsenal reversión (cuando N es grande y M es pequeño) debido a la localidad de caché, ya que estamos bucle sobre la matriz en pequeños pasos.

Nota final: si la matriz es pequeño, triples inversa es simple. Si usted tiene un arsenal grande, vale la pena la sobrecarga de la elaboración de la GCD para reducir el número de movimientos en un factor de 2. Ref: http://www.geeksforgeeks.org/array-rotation/

Answer 4

configurarlo con punteros, y se tarda muy poco tiempo. Cada elemento apunta al siguiente, y el "último" (no hay un último; después de todo, se dijo que era circular) apunta a la primera. Un puntero al "inicio" (primer elemento), y tal vez una longitud, y que tienen su matriz. Ahora, para hacer su turno, que acaba de caminar el puntero de su inicio a lo largo del círculo.

Pide un buen algoritmo, y se obtiene ideas sensibles. Pide rápido , y se obtiene ideas raras!

Answer 5

Este algoritmo se ejecuta en tiempo O (n) y O (1) espacio. La idea es trazar cada grupo cíclico en el cambio (contados por la variable 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

Este código funciona bien incluso en negativo turno k

Answer 7

función C arrayShiftRight. Si cambio es negativo dejó la matriz cambios de función. Está optimizado para menos uso de memoria. tiempo de ejecución es 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 solución muy simple. Esta es una manera muy rápida, aquí utilizo una serie temporal con el mismo tamaño o original y adjuntar a la variable original al final. Este uso método O (n) la complejidad temporal y O (n) la complejidad espacio y es muy sencillo de implementar.

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

En función de la estructura de datos que utilice, puede hacerlo en O (1). Creo que la forma más rápida es para mantener la matriz en forma de una lista enlazada, y tienen una tabla hash que puede traducir entre el "índice" de la matriz de "puntero" a la entrada. De esta manera usted puede encontrar las cabezas y las colas relevantes en O (1), y hacer la reconexión en O (1) (y actualizar la tabla de dispersión después del cambio en O (1)). Por supuesto, esto sería una solución muy "sucio", pero si todo lo que le interesa es la velocidad del cambio, que va a hacer (en la costa de inserción más largos y las operaciones de búsqueda en la matriz, pero todavía permanecerá O ( 1))

Si usted tiene los datos en una matriz pura, no creo que pueda evitar O (n).

Codificación-sabia, que depende de qué idioma que está utilizando.

En Python, por ejemplo, usted podría "rebanada" que (se supone n es el tamaño de turno):

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

(sé que las operaciones de búsqueda de hash es, en teoría, no O (1) pero estamos práctico aquí y no teórico, al menos eso espero ...)

Answer 10

Esto debería funcionar para cambiar una forma circular arry: Entrada: {1, 2, 3, 5, 6, 7, 8}; Valor de salida presente en matriz después de los 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

Aquí es un general simple y eficiente en su lugar la función de rotar en C ++, a menos de 10 líneas.

, que es un extracto de mi respuesta a otra pregunta. Cómo rotar una matriz?

#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

Mantener dos índices a la matriz, un índice comienza desde el principio de la matriz al final de la matriz. Otro índice comienza desde la posición Mes de la última y los bucles a través de los últimos M elementos cualquier número de veces. Toma O (n) en todo momento. No se requiere espacio adicional.

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

Vea esto si usted está interesado en una aplicación Java:

Perlas de programación: Circular izquierda / derecha Shift Operación

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

Rubí ejemplo:

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

En teoría, la más rápida es un bucle como este:

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

En la práctica, debe perfil it y ver.

Answer 17

Aquí es 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()] );
}

Por supuesto que no es tan elegante como la famosa solución de tres veces inversa, pero dependiendo de la máquina se puede rápida similary.

Answer 18

circleArray tiene algunos errores y no funciona en todos los casos!

El bucle debe continuar while i1 < i2 NO 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 amigo mío mientras yo bromeando le preguntó cómo pasar una matriz, que se acercó con esta solución (ver enlace Ideone), la suya ahora que he visto, alguien parece un poco esotérico.

aquí .

#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

Este método va a hacer este trabajo:

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

Al igual que en @IsaacTurner y no es tan elegante, debido a la copia innecesaria, pero la aplicación es bastante corto.

La idea - Un elemento de permuta en el índice 0 con el elemento B que se encuentra en el destino de A. Ahora B es primero. Intercambiarlo con el elemento C que se encuentra en el destino de B. Continuar hasta que el destino no está en 0.

Si el máximo común divisor no es 1, entonces usted no está terminado todavía -. Que necesita para continuar el intercambio, pero ahora usando el índice 1 en el punto inicial y final

Continuar hasta su posición de partida no es el 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

Aquí está mi solución en Java, que me consiguió el 100% Puntuación de tareas y el 100% en la corrección 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];
    }
}

Tenga en cuenta que a pesar de ver dos bucles for, la iteración en toda la matriz se realiza sólo una vez.

Answer 23

Swift versión 4 para el cambio de hilera izquierda.

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
}

Por ejemplo, si la matriz de entrada es a = [1, 2, 3, 4, 5], y izquierda compensar cambio es d = 4, entonces resultado será [5, 1, 2, 3, 4]