Algorithme de rotation d'une matrice en temps linéaire

Question

Comment faire pivoter un tableau d'entiers de i fois en utilisant la fonction swap uniquement en temps linéaire.

Answer 1

Vous pouvez le faire dans le temps linéaire en utilisant un assistant inverse().

// 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) 
{ 
    ... 
} 

La mise en œuvre au moyen de swaps reverse(int array[], int pos_from, int pos_to) est laissé comme un exercice pour le lecteur. Astuce: Cela peut être fait en temps linéaire.

Answer 2

une naïve mise en œuvre de pseudocode:

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

se déplace à plusieurs reprises le dernier élément à l'avant, l'arrêt avant de se déplacer quoi que ce soit déplacé auparavant à l'avant

Answer 3

pourquoi seule fonction d'échange?

O (n) dans le temps et l'espace:

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<arr.length; i++) 
    tmp[(i+rotateCount)%arr.length]=arr[i]; 
arr = tmp; 

alert(arr); 

Answer 4

Disons que nous avons une fonction appelée arr_reverse(arr,i,j) qui inverse les éléments du tableau arr entre l'indice i et j en utilisant la fonction swap.

Exemple:

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

alors la fonction retournera:

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

La mise en œuvre de cette fonction est simple et est O(N).

Utilisons maintenant cette fonction pour faire pivoter la matrice.

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,l-k,l-1) which is arr_reverse(arr,3,4) 
we get {1,2,3,5,4} 
       ^^^ 

Step 2: Call arr_reverse(arr,0,l-k-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} 
     ^^^^^^^^^ 

L'ensemble du processus utilise arr_reverse 3 fois, ce qui en fait O(N)

Answer 5

Mieux utiliser une fonction directe et simple, la complexité N:

int rotate(int* a,int DIM,int rn,int* b) { 
    int i; //counter 
    for(i=0;i<DIM;i++){ // looping through the array 
     b[(i+rn)%len]=a[i]; // copying the values in the b array=a shifted with rn(+ for right or - for left shifting 
} 

Answer 6

En utilisant O temps linéaire (2N + m), et l'espace constant O (4). m = GCD (n, p)

Il est jusqu'à 50% plus rapide que l'approche de permutation, car l'échange nécessite d'écrire O (N) fois à un moment.

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<n ? j+p : j+p-n, count++) 
     A[i]=A[j]; 
    A[i]=t; count++; 
} 

Answer 7

est ici une meilleure solution, d'une autre nature que les autres. Cela implique moins d'échanges de tableaux que les autres.Python:

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 

Answer 8

/* 
* 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]); 
     } 
    } 
} 

Answer 9

/* 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 <iostream> 
#include <algorithm> 
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 
*/ 

Answer 10

l'aide de swaps seulement, suivant est un implémentation C++

template<class T> 
void rotate_array(std::vector<T> *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)); 
    } 
    } 
} 

Vous pouvez en lire davantage à http://pointer-overloading.blogspot.in/2013/09/algorithms-rotating-one-dimensional.html

Answer 11

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

}

Answer 12

Voici un petit extrait des thats travaux dans O (n), écrit en JavaScript. Le keyconcept est, que vous devez toujours travailler avec l'élément remplacé.

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)) 

Answer 13

Une méthode O(1) d'y parvenir, 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 

Ceci est basé sur this answer about using a 1-based list in python. Cela a le léger problème que si vous essayez d'indexer un élément à la fin de la liste, il retournera les éléments du (nouveau) début, et les indices négatifs inférieurs à la taille moins le décalage ne fonctionnera pas .

Answer 14

public static String rotateKTimes(String str,int k){ 
    int n = str.length(); 

    //java substring has O(n) complexity 
    return str.substring(n-k) + str.substring(0,n-k); 
} 

Answer 15

Voici ma réponse à l'aide js espérons que cette aide où k est le nombre de rotations que vous souhaitez préforme

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; 

Answer 16

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

} 

Doug McIlroy’s Handwaving Description

Answer 17

Simple Solution in O(n) time and using O(1) space: 
for e.g 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<k;j++) { 
    for(int i=start;i<a.length;i+=k) 
    { 
     int tmp=a[i]; 
     a[i]=last; 
     last=tmp; 
    } 
    start--; 
    if (start<=0) break; 
    } 
    a[0]=last; 
    return a; 
} 

Answer 18

Pour rotation circulaire droite.

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