Rotar una matriz de enteros con un algoritmo O (n) [cerrado]

10

Escriba una función que rote una matriz entera por un número dado k. Los elementos k desde el final deben moverse hasta el comienzo de la matriz, y todos los demás elementos deben moverse hacia la derecha para hacer el espacio.

La rotación debe hacerse en el lugar.

El algoritmo no debe ejecutarse en más de O (n), donde n es el tamaño de la matriz.

También se debe utilizar una memoria constante para realizar la operación.

Por ejemplo,

si la matriz se inicializa con elementos arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}

rotar (arr, 3) dará como resultado que los elementos sean {7, 8, 9, 1, 2, 3, 4, 5, 6}

rotar (arr, 6) dará como resultado {4, 5, 6, 7, 8, 9, 1, 2, 3}

microbiano
fuente
1
¿Qué se entiende por memoria constante aquí? Seguramente se requiere al menos memoria O (n) como mínimo para almacenar la matriz que se está procesando, haciendo imposible el uso de la memoria O (1) .
Ad Hoc Garf Hunter
2
Estoy votando para cerrar esta pregunta como fuera de tema porque las preguntas sin un criterio ganador primario objetivo están fuera de tema, ya que hacen imposible decidir indiscutiblemente qué entrada debe ganar. No hay absolutamente ninguna razón para que esto sea un concurso de popularidad.
James
Votado para cerrar. De la wiki del concurso de popularidad ( aquí ), "Da libertad a los participantes para decidir qué hacer en partes cruciales y los incentiva a usar esta libertad". No creo que dejar el desafío abierto a ningún algoritmo cuente como alentar la creatividad para un desafío tan simple, al menos no en la medida en que funcione como un popcon. Esto sería más adecuado como un desafío de código de golf .
mbomb007

Respuestas:

18

C (104)

void reverse(int* a, int* b)
{
    while (--b > a) {
        *b ^= *a;
        *a ^= *b;
        *b ^= *a;
        ++a;
    }
}

void rotate(int *arr, int s_arr, int by)
{
    reverse(arr, arr+s_arr);
    reverse(arr, arr+by);
    reverse(arr+by, arr+s_arr);
}

Minified:

v(int*a,int*b){while(--b>a){*b^=*a;*a^=*b;*b^=*a++;}}r(int*a,int s,int y){v(a,a+s);v(a,a+y);v(a+y,a+s);}
Ben Voigt
fuente
44
Debería haber escrito la condición del bucle while comoa <-- b
solo el
Solía ​​haber un momento en que los programas C ganaban concursos de popularidad ...
Anubian Noob
¡Eress el mejor! Qué elegante y optimizado. ¿Podrías hacer esto con bit array?
9

APL (4)

¯A⌽B
  • A es el número de lugares para rotar
  • B es el nombre de la matriz a rotar

No estoy seguro de si APL realmente lo requería, pero en la implementación que he visto (lo interno de) esto tomaría un tiempo proporcional Ay una memoria constante.

Jerry Coffin
fuente
+1 si esto fuera golf :)
Glenn Teitelbaum
Sin embargo, no lo hace en su lugar.
marinus
@marinus: Ciertamente lo hace en las implementaciones que he visto.
Jerry Coffin
¿Cómo es esto una función? Podría ser {⍵⌽⍨-⍺}o {⌽⍺⌽⌽⍵}. En NARS2000 se puede escribir elegantemente como ⌽⍢⌽.
Adám
5

Aquí hay una versión C larga y sin aliento de la idea de Colin.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
  int t;
  if (a < b) {
    t = b; b = a; a = t;
  }
  while (b != 0) {
    t = a%b;
    a = b;
    b = t;
  }
  return a;
}

double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int s_arr = sizeof(arr)/sizeof(double);

/* We assume 1 <= by < s_arr */
void rotate(double *arr, int s_arr, int by) {
  int i, j, f;
  int g = gcd(s_arr,by);
  int n = s_arr/g;
  double t_in, t_out;

  for (i=0; i<g; i++) {
    f = i;
    t_in = arr[f + s_arr - by];
    for (j=0; j<n; j++) {
      t_out = arr[f];
      arr[f] = t_in;
      f = (f + by) % s_arr;
      t_in = t_out;
    }
  }
}

void print_arr(double *arr, int s_arr) {
  int i;
  for (i=0; i<s_arr; i++) printf("%g ",arr[i]);
  puts("");
}

int main() {
  double *temp_arr = malloc(sizeof(arr));
  int i;

  for (i=1; i<s_arr; i++) {
    memcpy(temp_arr, arr, sizeof(arr));
    rotate(temp_arr, s_arr, i);
    print_arr(temp_arr, s_arr);
  }
}
Stephen Montgomery-Smith
fuente
No parece una solución de memoria constante, ¿verdad?
microbio
Sí, es una solución de memoria constante. El material "mal colocado" es una copia temporal de la matriz para que pueda copiar los datos originales una y otra vez, de modo que pueda probar diferentes cantidades de rotación.
Stephen Montgomery-Smith
Lo que hace la rotación real es la función "rotar". Utiliza 5 enteros y dos dobles. También llama a una función "gcd" que usa un número entero y usa como máximo operaciones O (log (n)).
Stephen Montgomery-Smith
Entendido. Subí tu respuesta.
microbio el
@ StephenMontgomery-Smith: ¿cómo es esta O(log(n))operación? Mire a byser 1, su bucle `j 'es s_arr / go N - estas son operaciones O (N)
Glenn Teitelbaum
3

C

No estoy seguro de cuál es el criterio, pero como me divertí con el algoritmo, aquí está mi entrada:

void rotate(int* b, int size, int shift)
{
    int *done;
    int *p;
    int i;
    int saved;
    int c;

    p = b;
    done = p;
    saved = *p;
    for (i = 0; i < size; ++i) {
        c = saved;
        p += shift;
        if (p >= b+size) p -= size;
        saved = *p;
        *p = c;
        if (p == done) {
            p += 1;
            done = p;
            saved = *p;
        }
    }
}

Lo jugaré golf por una buena medida también; 126 bytes, se pueden acortar:

void r(int*b,int s,int n){int*d,*p,i,t,c;d=p=b;t=*p;for(i=0;i<s;++i){c=t;p+=n;if(p>=b+s)p-=s;t=*p;*p=c;if(p==d){d=++p;t=*p;}}}
treamur
fuente
3

No veo muchas soluciones de C ++ aquí, así que pensé en probar esta, ya que no cuenta los caracteres.

Esta es la verdadera rotación "en el lugar", por lo que utiliza 0 espacio adicional (excepto técnicamente intercambio y 3 ints) y dado que el bucle es exactamente N, también cumple la complejidad O (N).

template <class T, size_t N>
void rot(std::array<T,N>& x, int shift)
{
        size_t base=0;
        size_t cur=0; 
        for (int i = 0; i < N; ++i)
        {
                cur=(cur+shift)%N; // figure out where we are going
                if (cur==base)     // exact multiple so we have to hit the mods when we wrap
                {
                        cur++;
                        base++;
                }
                std::swap(x.at(base), x.at(cur)); // use x[base] as holding area
        }
}
Glenn Teitelbaum
fuente
Nota: a propósito no lo usé std::rotateporque ese tipo de derrota el propósito
Glenn Teitelbaum
2

Si realiza cada uno de los posibles ciclos de rotaciones por n a su vez (hay GCD (n, len (arr)) de estos), entonces solo necesita una copia temporal única de un elemento de matriz y algunas variables de estado. Así, en Python:

from fractions import gcd

def rotate(arr, n):
    total = len(arr)
    cycles = gcd(n, total)
    for start in range(0, cycles):
        cycle = [i % total for i in range(start, abs(n * total) / cycles, n)]
        stash = arr[cycle[-1]]
        for j in reversed(range(1, len(cycle))):
            arr[cycle[j]] = arr[cycle[j - 1]]
        arr[cycle[0]] = stash
Colin Watson
fuente
1
Creo que tiene la idea correcta, pero su cyclevariable no tiene un tamaño constante. Tendrás que generar esta matriz a medida que avanzas.
Keith Randall el
2

C (137 caracteres)

#include <stdio.h>

void rotate(int * array, int n, int k) {
    int todo = (1<<n+1)-1;
    int i = 0, j;
    int tmp = array[0];

    while (todo) {
        if (todo & 1<<i) {
            j = (i-k+n)%n;
            array[i] = todo & 1<<j ? array[j] : tmp;
            todo -= 1<<i;
            i = j;
        } else tmp = array[++i];
    }
}

int main() {
    int a[] = {1,2,3,4,5,6,7,8,9};
    rotate(a, 9, 4);
    for (int i=0; i<9;i++) printf("%d ", a[i]);
    printf("\n");
}

Función rotateminimizada a 137 caracteres:

void r(int*a,int n,int k){int m=(1<<n+1)-1,i=0,j,t=a[0];while(m)if(m&1<<i){j=(i-k+n)%n;a[i]=(m&1<<j)?a[j]:t;m-=1<<i;i=j;}else t=a[++i];}
craesh
fuente
2

Factor tiene un tipo incorporado para matrices rotativas <circular>, por lo que esta es realmente una operación O (1):

: rotate ( circ n -- )
    neg swap change-circular-start ;

IN: 1 9 [a,b] <circular> dup 6 rotate >array .
{ 4 5 6 7 8 9 1 2 3 }
IN: 1 9 [a,b] <circular> dup 3 rotate >array .
{ 7 8 9 1 2 3 4 5 6 }

Un factor menos engañoso equivalente a la impresionante solución C de Ben Voigt:

: rotate ( n s -- ) 
    reverse! swap cut-slice [ reverse! ] bi@ 2drop ;

IN: 7 V{ 0 1 2 3 4 5 6 7 8 9 } [ rotate ] keep .
V{ 3 4 5 6 7 8 9 0 1 2 }
Björn Lindqvist
fuente
2

JavaScript 45

Fui para el golf de todos modos porque me gusta el golf. Está al máximo O (N) siempre que tsea ​​<= tamaño de la matriz.

function r(o,t){for(;t--;)o.unshift(o.pop())}

Para manejar tcualquier proporción en O (N) se puede usar lo siguiente (con un peso de 58 caracteres):

function r(o,t){for(i=t%o.length;i--;)o.unshift(o.pop())}

No regresa, edita la matriz en su lugar.

George Reith
fuente
1
+1 parar(o,t) => rot
Conor O'Brien el
1

REBELDE - 22

/_(( \d+)+)( \d+)/$3$1

Entrada: k expresado como un entero unario usando _como un dígito, seguido de un espacio, luego un conjunto de enteros delimitados por espacios.

Salida: Un espacio, luego la matriz gira.

Ejemplo:

___ 1 2 3 4 5/_(( \d+)+)( \d+)/$3$1

Estado final:

 3 4 5 1 2

Explicación:

En cada iteración, reemplaza uno _y una matriz [array] + tailcon tail + [array].

Ejemplo:

___ 1 2 3 4 5
__ 5 1 2 3 4
_ 4 5 1 2 3
 3 4 5 1 2
Kendall Frey
fuente
No creo que esto sea O (n). Copiar una matriz es O(n), y lo haces nveces.
Ben Voigt
1

Java

public static void rotate(int[] arr, int by) {
    int n = arr.length;
    int i = 0;
    int j = 0;
    while (i < n) {
        int k = j;
        int value = arr[k];
        do {
            k = (k + by) % n;
            int tmp = arr[k];
            arr[k] = value;
            value = tmp;
            i++;
        } while (k != j);
        j++;
    }
}

Demostración aquí .

Javascript Minificado , 114 :

function rotate(e,r){n=e.length;i=0;j=0;while(i<n){k=j;v=e[k];do{k=(k+r)%n;t=e[k];e[k]=v;v=t;i++}while(k!=j);j++}}
ValarDohaeris
fuente
1

Haskell

Esto es en realidad θ (n), ya que la división es θ (k) y la unión es θ (nk). Aunque no estoy seguro acerca de la memoria.

rotate 0 xs = xs
rotate n xs | n >= length xs = rotate (n`mod`(length xs)) xs
            | otherwise = rotate' n xs

rotate' n xs = let (xh,xt) = splitAt n xs in xt++xh
Archaephyrryx
fuente
1

Python 3

from fractions import gcd
def rotatelist(arr, m):
    n = len(arr)
    m = (-m) % n # Delete this line to change rotation direction
    for i0 in range(gcd(m, n)):
        temp = arr[i0]
        i, j = i0, (i0 + m) % n
        while j != i0:
            arr[i] = arr[j]
            i, j = j, (j + m) % n
        arr[i] = temp

Memoria constante
O (n) complejidad de tiempo

AMK
fuente
0

Pitón

def rotate(a, n): a[:n], a[n:] = a[-n:], a[:-n] 
Madison May
fuente
¿Utilizará esto memoria constante?
SztupY
Hmm ... no estoy seguro.
Madison mayo
No es una operación de memoria constante.
microbio
Shucks Buena llamada ...
Madison May
0

pitón

   import copy
    def rotate(a, r):
        c=copy.copy(a);b=[]
        for i in range(len(a)-r):   b.append(a[r+i]);c.pop();return b+c
saykou
fuente
Copiar la matriz no es un espacio constante. La respuesta de @ MadisonMay hace esencialmente lo mismo que este código con muchos menos caracteres.
Blckknght
0

vb.net O (n) (no memoria constante)

Function Rotate(Of T)(a() As T, r As Integer ) As T()     
  Dim p = a.Length-r
  Return a.Skip(p).Concat(a.Take(p)).ToArray
End Function
Adam Speight
fuente
0

Rubí

def rotate(arr, n)
  arr.tap{ (n % arr.size).times { arr.unshift(arr.pop) } }  
end
OI
fuente
0

C (118)

Probablemente fue demasiado indulgente con algunas de las especificaciones. Utiliza memoria proporcional a shift % length. También puede girar en la dirección opuesta si se pasa un valor de desplazamiento negativo.

r(int *a,int l,int s){s=s%l<0?s%l+l:s%l;int *t=malloc(4*s);memcpy(t,a+l-s,4*s);memcpy(a+s,a,4*(l-s));memcpy(a,t,4*s);}
cardinaliti
fuente
0

Pitón 2, 57

def rotate(l,n):
 return l[len(l)-n:len(l)]+l[0:len(l)-n]

Si solo l[-n:len(l)-n]funcionara como lo esperaría. Simplemente regresa []por alguna razón.

cjfaure
fuente
0
def r(a,n): return a[n:]+a[:n]

¿Podría alguien verificar si esto realmente cumple con los requisitos? Creo que sí, pero no he estudiado CS (todavía).

ɐɔıʇǝɥʇuʎs
fuente
0

C ++, 136

template<int N>void rotate(int(&a)[N],int k){auto r=[](int*b,int*e){for(int t;--e>b;t=*b,*b++=*e,*e=t);};r(a,a+k);r(a+k,a+N);r(a,a+N);}
Mattnewport
fuente
0

Java

Intercambie los últimos k elementos con los primeros k elementos, y luego rote los elementos restantes por k. Cuando le queden menos de k elementos al final, gírelos por k% del número de elementos restantes. No creo que nadie arriba haya tomado este enfoque. Realiza exactamente una operación de intercambio para cada elemento, hace todo en su lugar.

public void rotate(int[] nums, int k) {
    k = k % nums.length; // If k > n, reformulate
    rotate(nums, 0, k);
}

private void rotate(int[] nums, int start, int k) {
    if (k > 0) {
        if (nums.length - start > k) { 
            for (int i = 0; i < k; i++) {
                int end = nums.length - k + i;
                int temp = nums[start + i];
                nums[start + i] = nums[end];
                nums[end] = temp;
            }
            rotate(nums, start + k, k); 
        } else {
            rotate(nums, start, k % (nums.length - start)); 
        }
    }
}
Matthew Saltz
fuente
0

Perl 5 , 42 bytes

sub r{$a=pop;map{unshift@$a,pop@$a}1..pop}

Pruébalo en línea!

La subrutina toma la distancia para rotar como el primer parámetro y una referencia a la matriz como el segundo. El tiempo de ejecución es constante en función de la distancia de rotación. El tamaño de la matriz no afecta el tiempo de ejecución. La matriz se modifica en su lugar eliminando un elemento de la derecha y colocándolo a la izquierda.

Xcali
fuente