Algoritmo para rotar una matriz en tiempo lineal

Cómo rotar una matriz de enteros por i veces usando la función de swap solo en tiempo lineal.

Puedes hacer esto en tiempo lineal usando un helper inverso ().

 // rotate array of size=size, by n positions void rotate(int array[], int size, int n) { // reverse array[0...size-1] reverse(array, 0, size-1); // reverse A[0...n-1] reverse(array, 0, n-1); // reverse A[n...size-1] reverse(array, n, size-1); } // reverse elements in the array[pos_from ... pos_to] void reverse(int array[], int pos_from, int pos_to) { ... } 

Implementar reverse(int array[], int pos_from, int pos_to) utilizando swaps se deja como un ejercicio para el lector. Sugerencia: esto se puede hacer en tiempo lineal.

Digamos que tenemos una función llamada arr_reverse(arr,i,j) que invierte los elementos de la matriz arr entre el índice i y j usando la función swap .

Ejemplo:

 arr = {1,2,3,4,5} i = 0 j = 2 

entonces la función volverá:

 {3,2,1,4,5} ^^^^^ 

La implementación de esta función es directa y es O(N) .

Ahora usemos esta función para hacer girar la matriz.

 arr = {1,2,3,4,5} // input array k = 2 // amount of right rotation result = {4,5,1,2,3} // expected result l = 5 // length of array. Step 1: Call arr_reverse(arr,lk,l-1) which is arr_reverse(arr,3,4) we get {1,2,3,5,4} ^^^ Step 2: Call arr_reverse(arr,0,lk-1) which is arr_reverse(arr,0,2) we get {3,2,1,5,4} ^^^^^ Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4) we get {4,5,1,2,3} ^^^^^^^^^ 

Todo el proceso utiliza arr_reverse 3 veces, por lo que es O(N)

Aquí hay una mejor solución, de una naturaleza diferente a las demás. Implica menos cambios de matriz que los demás. Pitón:

 import fractions # rotates an array in-place i positions to the left, in linear time def rotate(arr,i): n = len(arr) reps = fractions.gcd(n,i) swaps = n / reps for start in xrange(reps): ix = start tmp = arr[ix] for s in xrange(swaps-1): previx = ix ix = (ix + i) % n arr[previx] = arr[ix] arr[ix] = tmp return arr 

Usando tiempo lineal O (2N + m), y espacio constante O (4). m = GCD (n, p)

Es hasta un 50% más rápido que el enfoque de intercambio, ya que el intercambio requiere escribir O (N) veces en un temporal.

http://www.eis.mdx.ac.uk/staffpages/r_bornat/oldteaching/I2A/slides%209%20circshift.pdf

 for (m=0, count=0; count!=n; m++) { type t=A[m]; for (i=m, j=m+p; j!=m; i=j, j = j+p 

una implementación de pseudocódigo ingenua:

 for (n = 0; n < i; n++) { for (j = array.length-1; j > n; j--) swap(j, j-1) } 

Mueve repetidamente el último elemento hacia el frente, deteniéndolo antes de mover cualquier elemento previamente movido al frente

Mejor utilizar una función directa y simple, complejidad N:

 int rotate(int* a,int DIM,int rn,int* b) { int i; //counter for(i=0;i 

¿por qué solo cambiar la función?

O (n) en tiempo y espacio:

 var rotateCount = 1; var arr = new Array(1,2,3,4,5,6,7,8,9,10); tmp = new Array(arr.length); for (var i = 0; i 
 /* Q: How can we shift/rotate an array in place? A: "in place" means O(1) space complexity, so we need to do some trick */ #include  #include  using namespace std; void ArrayRotate(int a[], int n, int k) { if (n < 1 || k % n == 0 ) return; k %= n; if (k < 0) k += n; reverse(a, a+k); reverse(a+k, a+n); reverse(a, a+n); } void PrintArray(int a[], int n) { for ( int i = 0 ; i < n; ++i) cout << a[i] << " "; cout << endl; } int main() { int a[] = { 1, 2 , 3, 4, 5 }; int n = sizeof(a)/sizeof (a[0]); PrintArray(a, n); ArrayRotate(a, n, 2); PrintArray(a, n); return 0; } /* Output: 1 2 3 4 5 3 4 5 1 2 */ 

usando solo swap, siguiente es una implementación de C ++

 template void rotate_array(std::vector *array, int i) { int n = array->size(); i = i % n; int gcd_n_i = gcd(i, n); for (int j = 0; j < gcd_n_i; j++) { T first_element = array->at(j); for (int k = j; (k + i) % n != j; k = (k + i) % n) { std::swap(array->at(k), array->at((k + i) % n)); } } } 

Puede leer más sobre esto en http://pointer-overloading.blogspot.in/2013/09/algorithms-rotating-one-dimensional.html

 void reverse_array(int a[], int start, int end){ while(start < end){ int temp = a[start]; a[start] = a[end]; a[end] = temp; start++; end--; } 

}

 void rotate_array(int a[], int pivot, int len){ int i; /*Reverse the whole array */ reverse_array(a, 0, len); /* Reverse from 0 to pivot and pivot to end */ reverse_array(a,0, pivot); reverse_array(a,pivot+1,len); 

}

Aquí hay un pequeño fragmento que funciona en O (n), escrito en JavaScript. El concepto clave es que siempre debe trabajar con el artículo reemplazado.

 function swap(arr, a, v) { var old = arr[a]; arr[a] = v; return old; } function rotate(arr, n) { var length = arr.length; n = n % length; if(!n) return arr; for(var cnt = 0, index = 0, value = arr[index], startIndex = index; cnt < length; cnt++) { // Calc next index var nextIndex = mapIndex(index, n, length); // Swap value with next value = swap(arr, nextIndex, value) if(nextIndex == startIndex) { startIndex = index = mapIndex(index, 1, length); value = arr[index]; } else { index = nextIndex; } } return arr; } function mapIndex(index, n, length) { return (index - n + length) % length; } console.log(rotate([1,2,3,4,5,6,7,8,9], 5)) console.log(rotate([1,2,3,4,5,6], 2)) 

Un método de O(1) para lograr esto, en python:

 class OffsetList(list): __slots__ = 'offset' def __init__(self, init=[], offset=-1): super(OffsetList, self).__init__(init) self.offset = offset def __getitem__(self, key): return super(OffsetList, self).__getitem__(key + self.offset) def __setitem__(self, key, value): return super(OffsetList, self).__setitem__(key + self.offset, value) def __delitem__(self, key): return super(OffsetList, self).__delitem__(key + self.offset) def index(self, *args): return super(OffsetList, self).index(*args) - self.offset 

Esto se basa en esta respuesta sobre el uso de una lista basada en 1 en python .

Esto tiene la ligera falla de que si intenta indexar un elemento del final de la lista, devolverá ítems del (nuevo) comienzo, y las indicaciones negativas menores que el tamaño menos el desplazamiento no funcionarán.

aquí está mi respuesta usando js espero que esto ayude donde k es el número de rotaciones que desea preformar

  var arrayRoatate=function(array,k){ for(;k>0;k--) { var nextElementValue=undefined; for (var i = 0; i < array.length; i=i+2) { var nextElement = i + 1; if (nextElement >= array.length) nextElement = nextElement - array.length; var tmp=array[i]; if(nextElementValue!==undefined) array[i]=nextElementValue nextElementValue=array[nextElement]; array[nextElement]=tmp; } } return array; 
 public int[] shift(int[] A, int K) { int N = A.length; if (N == 0) return A; int mid = -K % N; if (mid < 0) mid += N; if (mid == 0) return A; reverseSubArray(A, 0 , mid - 1); reverseSubArray(A, mid , N - 1); reverseSubArray(A, 0 , N - 1); return A; } private void reverseSubArray(int[] A, int start , int end){ int i = 0; int tmp; while (i < (end - start + 1) / 2) { tmp = A[i + start]; A[i + start] = A[end - i]; A[end - i] = tmp; i++; } } 

Descripción de Hand Waving de Doug McIlroy

 /* * To change this template, choose Tools | Templates * and open the template in the editor. */ package rotateinlineartime; /** * * @author Sunshine */ public class Rotator { void reverse(int a[], int n) { for (int i = 0; i <= n - 1; i++) { int temp; temp = a[i]; a[i] = a[n - 1]; a[n - 1] = temp; n--; } printArray(a); } void printArray(int a[]) { for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } } } 

Para rotación circular a la derecha.

 public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int k = scan.nextInt() % n; int q = scan.nextInt(); int arr[] = new int[n]; for (int i = 0; i < n; i++) { int a = i + k; int pos = (a < n) ? a : a - n; arr[pos] = scan.nextInt(); } for (int j = 0; j < q; j++) { System.out.println(arr[scan.nextInt()]); } } 
 public static String rotateKTimes(String str,int k){ int n = str.length(); //java substring has O(n) complexity return str.substring(nk) + str.substring(0,nk); } 
 Simple Solution in O(n) time and using O(1) space: for eg 1,2,3,4,5,6,7 rotating 2 times start with index 2, store a[0] as last Iteration 1: 1,2,1,4,3,6,5 (1-->3-->5-->7) Iteration 2: 1,7,1,2,3,4,5 (2-->4-->6) replace 1 with 6 (last value). public int[] roatateArray(int[] a,int k) { int last = a[0]; int start = k; for(int j=0;j