algorithm - resueltos - El algoritmo más rápido para la matriz de tamaño N de cambio de círculo para la posición M

ejercicios resueltos de matlab programacion pdf

Question

¿Cuál es el algoritmo más rápido para la matriz de cambio de círculo para m posiciones?
Por ejemplo [3 4 5 2 3 1 4] shift m = 2 posiciones debe ser [1 4 3 4 5 2 3]

Muchas gracias

Answer 1

Solucion optima

Pregunta más rápida. Revertir tres veces es más simple pero mueve cada elemento exactamente dos veces, toma O (N) tiempo y O (1) espacio. Es posible desplazar en círculo una matriz moviendo cada elemento exactamente una vez también en O (N) tiempo y O (1) espacio.

Idea

Podemos desplazar en círculo un conjunto 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 de 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 se escribe una vez.

Diagrama de desplazamiento N=9, M=3

El primer ciclo se muestra en negro con números que indican el orden de las operaciones. El segundo y tercer ciclo se muestran en gris.

La cantidad de ciclos requeridos es el Divisor Común más Grande (GCD) de N y M Si el GCD es 3, comenzamos un ciclo en cada uno de {0,1,2} . El cálculo del GCD es rápido con el algoritmo Binario GCD .

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 frente a la inversión de matriz (cuando N es grande y M es pequeño) debido a la localidad de caché, ya que estamos recorriendo la matriz en pequeños pasos.

Nota final: si tu matriz es pequeña, el triple reverso es simple. Si tiene una matriz grande, vale la pena sobrecargar el GCD para reducir el número de movimientos por un factor de 2. Ref: http://www.geeksforgeeks.org/array-rotation/

Answer 2

Aquí está mi solución en Java que me dio 100% Task Score y 100% de exactitud en 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 solo se realiza una vez.

Answer 3

Aquí hay otro (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, no es tan elegante como la famosa solución inversa de tres veces, pero dependiendo de la máquina puede ser similarmente rápida .

Answer 4

C función arrayShiftRight. Si shift es negativo, la función desplaza la matriz hacia la izquierda. Está optimizado para menos uso de memoria. El 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 5

Configúrelo con punteros y no demorará casi nada. Cada elemento apunta al siguiente, y el "último" (no hay último, después de todo, dijiste que era circular) apunta al primero. Un puntero al "inicio" (primer elemento), y tal vez una longitud, y usted tiene su matriz. Ahora, para hacer su turno, simplemente camina su puntero de inicio a lo largo del círculo.

Pide un buen algoritmo y obtienes ideas sensatas. ¡Pide el más rápido y obtienes ideas raras!

Answer 6

Consulte esto si está interesado en una implementación de Java:

Perlas de programación: operación de desplazamiento circular izquierda / derecha

Answer 7

Dependiendo de la estructura de datos que use, puede hacerlo en O (1). Creo que la forma más rápida es mantener la matriz en forma de una lista vinculada, y tener una tabla hash que puede traducir "índice" en la matriz a "puntero" a la entrada. De esta forma, puede encontrar las caras y las colas correspondientes en O (1), y hacer la reconexión en O (1) (y actualizar la tabla hash después del cambio en O (1)). Esto, por supuesto, sería una solución muy "desordenada", pero si todo lo que le interesa es la velocidad del cambio, eso hará (a expensas de una inserción y búsqueda más largas en el conjunto, pero seguirá siendo O ( 1))

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

En lo que respecta a la codificación, depende del idioma que estés usando.

En Python, por ejemplo, podrías "cortarlo" (suponiendo que n es el tamaño del desplazamiento):

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

(Sé que la búsqueda de hash no es en teoría O (1) pero somos prácticos aquí y no teóricos, al menos eso espero ...)

Answer 8

En teoría, el más rápido es un ciclo 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 perfilarlo y ver.

Answer 9

Es solo una cuestión de representación. Mantenga el índice actual como una variable entera y al atravesar la matriz use el operador de módulo para saber cuándo se debe ajustar. El cambio solo está cambiando el valor del índice actual, envolviéndolo 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 10

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

Este método hará 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 12

Esto debería funcionar para desplazar un arry circularmente: Entrada: {1, 2, 3, 5, 6, 7, 8}; Valor de salida presente en array 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 13

Mantenga dos índices en la matriz, un índice comienza desde el principio de la matriz hasta el final de la matriz. Otro índice comienza desde la posición M del último y recorre los últimos M elementos cualquier cantidad de veces. Toma O (n) en todo momento. No 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 14

Ruby 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 15

Si quiere O (n) tiempo y no requiere uso de memoria adicional (ya que se especificó el arreglo), use el algoritmo del libro de Jon Bentley, "Programming Pearls 2nd Edition". Cambia todos los elementos dos veces. No es tan rápido como usar listas enlazadas, pero usa 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 (anArray, startIndex, endIndex) invierte el orden de los elementos de startIndex a endIndex, inclusive.

Answer 16

Similar a @IsaacTurner y no tan elegante debido a la copia innecesaria, pero la implementación es bastante corta.

La idea: intercambie el elemento A en el índice 0 con el elemento B que se encuentra en el destino de A. Ahora B es el primero. Cambie con el elemento C que se encuentra en el destino de B. Continúe hasta que el destino no esté en 0.

Si el máximo divisor común no es 1, entonces aún no ha terminado: debe continuar intercambiando, pero ahora usa el índice 1 en su punto inicial y final.

Continúa hasta que tu posición inicial no sea el gcd.

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 17

Un amigo mío, mientras bromeaba, me preguntó cómo cambiar una matriz, se me ocurrieron estas soluciones (ver enlace ideone), ahora que he visto la tuya, alguien parece un poco esotérico.

Echa un vistazo here .

#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 18

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

El ciclo 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

Aquí hay una función de rotación general simple y eficiente en su lugar en C ++, menos de 10 líneas.

que se extrae de mi respuesta en 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 20

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 21

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 cambio negativo k