Dada una array M x N, transponga la array sin memoria auxiliar. Es fácil transponer una array usando una array auxiliar. Si la array tiene un tamaño simétrico, podemos transponer la array en su lugar reflejando la array 2D a lo largo de su diagonal (pruébelo usted mismo). ¿Cómo transponer una array de tamaño arbitrario en su lugar? Ver la siguiente array,
a b c a d g j d e f ==> b e h k g h i c f i l j k l
Según la numeración 2D en C/C++, el mapeo de ubicación correspondiente parece,
Org element New 0 a 0 1 b 4 2 c 8 3 d 1 4 e 5 5 f 9 6 g 2 7 h 6 8 i 10 9 j 3 10 k 7 11 l 11
Tenga en cuenta que el primer y el último elemento permanecen en su ubicación original. Podemos ver fácilmente que la transformación forma algunos ciclos de permutación.
- 1->4->5->9->3->1 – Total 5 elementos forman el ciclo
- 2->8->10->7->6->2 – Otros 5 elementos forman el ciclo
- 0 – Auto ciclo
- 11 – Autociclo
Del ejemplo anterior, podemos diseñar fácilmente un algoritmo para mover los elementos a lo largo de estos ciclos. ¿Cómo podemos generar ciclos de permutación? El número de elementos en ambas arrays es constante, dado por N = R * C, donde R es el recuento de filas y C es el recuento de columnas. Un elemento en la ubicación ol (ubicación anterior en la array R x C), movido a nl (ubicación nueva en la array C x R). Necesitamos establecer la relación entre ol, nl, R y C. Suponga que ol = A[o][oc] . En C/C++ podemos calcular la dirección del elemento como,
ol = or x C + oc (ignore base reference for simplicity)
Se debe mover a la nueva ubicación nl en la array transpuesta, digamos nl = A[nr][nc] , o en términos de C/C++
nl = nr x R + nc (R - column count, C is row count as the matrix is transposed)
Observe, nr = oc y nc = or , por lo que reemplazando estos por nl ,
nl = oc x R + or -----> [eq 1]
después de resolver la relación entre ol y nl , obtenemos
ol = or x C + oc
ol x R = or x C x R + oc x R
= or x N + oc x R (from the fact R * C = N)
= or x N + (nl - or) --- from [eq 1]
= or x (N-1) + nl
O,
nl = ol x R - or x (N-1)
Tenga en cuenta que los valores de nl y ol nunca van más allá de N-1 , por lo que considerando la división del módulo en ambos lados por ( N-1 ), obtenemos lo siguiente en función de las propiedades de congruencia,
nl mod (N-1) = (ol x R - or x (N-1)) mod (N-1)
= (ol x R) mod (N-1) - or x (N-1) mod(N-1)
= ol x R mod (N-1), since second term evaluates to zero
nl = (ol x R) mod (N-1), since nl is always less than N-1
Un lector curioso podría haber observado el significado de la relación anterior. Cada ubicación se escala por un factor de R (tamaño de fila). Es obvio a partir de la array que cada ubicación se desplaza por el factor escalado de R. El multiplicador real depende de la clase de congruencia de (N-1), es decir, el multiplicador puede ser tanto -ve como +ve el valor de la clase congruente. Por lo tanto, cada transformación de ubicación es una simple división de módulo. Estas divisiones de módulos forman permutaciones cíclicas. Necesitamos información de contabilidad para realizar un seguimiento de los elementos ya movidos. Aquí está el código para la transformación de array in situ,
Implementación:
C++
// C++ program for in-place matrix transpose
#include <bits/stdc++.h>
#define HASH_SIZE 128
using namespace std;
// A utility function to print a 2D array
// of size nr x nc and base address A
void Print2DArray(int *A, int nr, int nc)
{
for(int r = 0; r < nr; r++)
{
for(int c = 0; c < nc; c++)
{
cout<<setw(4)<<*(A + r*nc + c);
}
cout<<endl;
}
cout<<endl;
}
// Non-square matrix transpose of
// matrix of size r x c and base address A
void MatrixInplaceTranspose(int *A, int r, int c)
{
int size = r*c - 1;
int t; // holds element to be replaced,
// eventually becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int i; // iterator
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
i = 1; // Note that A[0] and A[size-1] won't move
while (i < size)
{
cycleBegin = i;
t = A[i];
do
{
// Input matrix [r x c]
// Output matrix
// i_new = (i*r)%(N-1)
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;
}
while (i != cycleBegin);
// Get Next Move (what about querying random location?)
for (i = 1; i < size && b[i]; i++)
;
cout << endl;
}
}
// Driver program to test above function
int main()
{
int r = 5, c = 6;
int size = r*c;
int *A = new int[size];
for(int i = 0; i < size; i++)
A[i] = i+1;
Print2DArray(A, r, c);
MatrixInplaceTranspose(A, r, c);
Print2DArray(A, c, r);
delete[] A;
return 0;
}
// This code is contributed by rrrtnx.
C
// Program for in-place matrix transpose
#include <stdio.h>
#include <iostream>
#include <bitset>
#define HASH_SIZE 128
using namespace std;
// A utility function to print a 2D array of size nr x nc and base address A
void Print2DArray(int *A, int nr, int nc)
{
for(int r = 0; r < nr; r++)
{
for(int c = 0; c < nc; c++)
printf("%4d", *(A + r*nc + c));
printf("\n");
}
printf("\n\n");
}
// Non-square matrix transpose of matrix of size r x c and base address A
void MatrixInplaceTranspose(int *A, int r, int c)
{
int size = r*c - 1;
int t; // holds element to be replaced, eventually becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int i; // iterator
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
i = 1; // Note that A[0] and A[size-1] won't move
while (i < size)
{
cycleBegin = i;
t = A[i];
do
{
// Input matrix [r x c]
// Output matrix
// i_new = (i*r)%(N-1)
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;
}
while (i != cycleBegin);
// Get Next Move (what about querying random location?)
for (i = 1; i < size && b[i]; i++)
;
cout << endl;
}
}
// Driver program to test above function
int main(void)
{
int r = 5, c = 6;
int size = r*c;
int *A = new int[size];
for(int i = 0; i < size; i++)
A[i] = i+1;
Print2DArray(A, r, c);
MatrixInplaceTranspose(A, r, c);
Print2DArray(A, c, r);
delete[] A;
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 7 13 19 25 2 8 14 20 26 3 9 15 21 27 4 10 16 22 28 5 11 17 23 29 6 12 18 24 30
Extensión: 17 – marzo – 2013 Algunos lectores identificaron similitud entre la transposición de array y la transformación de cuerdas . Sin mucha teoría estoy presentando el problema y la solución. En una array dada de elementos como [a1b2c3d4e5f6g7h8i9j1k2l3m4]. Conviértalo a [abcdefghijklm1234567891234]. El programa debe ejecutarse en su lugar. Lo que necesitamos es una transposición in situ. A continuación se muestra el código.
Implementación:
C++
#include <bits/stdc++.h>
#define HASH_SIZE 128
using namespace std;
typedef char data_t;
void Print2DArray(char A[], int nr, int nc) {
int size = nr*nc;
for(int i = 0; i < size; i++)
cout<<setw(4)<<*(A+i);
cout<<endl;
}
void MatrixTransposeInplaceArrangement(data_t A[], int r, int c) {
int size = r*c - 1;
data_t t; // holds element to be replaced, eventually becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int i; // iterator
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
i = 1; // Note that A[0] and A[size-1] won't move
while( i < size ) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix
// i_new = (i*r)%size
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;
} while( i != cycleBegin );
// Get Next Move (what about querying random location?)
for(i = 1; i < size && b[i]; i++)
;
cout << endl;
}
}
void Fill(data_t buf[], int size) {
// Fill abcd ...
for(int i = 0; i < size; i++)
buf[i] = 'a'+i;
// Fill 0123 ...
buf += size;
for(int i = 0; i < size; i++)
buf[i] = '0'+i;
}
void TestCase_01(void) {
int r = 2, c = 10;
int size = r*c;
data_t *A = new data_t[size];
Fill(A, c);
Print2DArray(A, r, c), cout << endl;
MatrixTransposeInplaceArrangement(A, r, c);
Print2DArray(A, c, r), cout << endl;
delete[] A;
}
int main() {
TestCase_01();
return 0;
}
// This code is contributed by rutvik_56.
C
#include <stdio.h>
#include <iostream>
#include <bitset>
#define HASH_SIZE 128
using namespace std;
typedef char data_t;
void Print2DArray(char A[], int nr, int nc) {
int size = nr*nc;
for(int i = 0; i < size; i++)
printf("%4c", *(A + i));
printf("\n");
}
void MatrixTransposeInplaceArrangement(data_t A[], int r, int c) {
int size = r*c - 1;
data_t t; // holds element to be replaced, eventually becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int i; // iterator
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
i = 1; // Note that A[0] and A[size-1] won't move
while( i < size ) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix
// i_new = (i*r)%size
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;
} while( i != cycleBegin );
// Get Next Move (what about querying random location?)
for(i = 1; i < size && b[i]; i++)
;
cout << endl;
}
}
void Fill(data_t buf[], int size) {
// Fill abcd ...
for(int i = 0; i < size; i++)
buf[i] = 'a'+i;
// Fill 0123 ...
buf += size;
for(int i = 0; i < size; i++)
buf[i] = '0'+i;
}
void TestCase_01(void) {
int r = 2, c = 10;
int size = r*c;
data_t *A = new data_t[size];
Fill(A, c);
Print2DArray(A, r, c), cout << endl;
MatrixTransposeInplaceArrangement(A, r, c);
Print2DArray(A, c, r), cout << endl;
delete[] A;
}
int main() {
TestCase_01();
return 0;
}
a b c d e f g h i j 0 1 2 3 4 5 6 7 8 9 a 0 b 1 c 2 d 3 e 4 f 5 g 6 h 7 i 8 j 9
++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++
Actualización 09-julio-2016: Notas sobre la complejidad del espacio y el orden de almacenamiento.
Después de mucho tiempo, se me ocurrió revisar este post. Algunos lectores señalaron preguntas válidas sobre cómo puede estar en el lugar (?) Cuando estamos usando un conjunto de bits como marcador ( hash en el código). Disculpas por la percepción incorrecta al mirar el título o el contenido del artículo. Mientras preparaba el contenido inicial, estaba pensando en una implementación ingenua utilizando el espacio auxiliar de al menos O(MN) necesario para transponer una array rectangular. El programa presentado anteriormente usa espacio constante ya que el tamaño del conjunto de bits se fija en el momento de la compilación. Sin embargo, para admitir el tamaño arbitrario de las arrays, necesitamos un tamaño de conjunto de bits de al menos un tamaño O (MN). Se puede usar un HashMap ( complejidad O(1) amortizada ) para marcar ubicaciones terminadas, pero la complejidad del peor de los casos de HashMap puede ser O(N) u O(log N)basado en la implementación. El costo del espacio de HashMap también aumenta según los elementos insertados. Tenga en cuenta que en el lugar se utilizó wrt matrix space .
Además, se asumió que la array se almacenará en ordenación principal de filas (ubicaciones contiguas en la memoria). El lector puede derivar las fórmulas, si la array está representada en orden de columna mayor por el lenguaje de programación (por ejemplo, Fortran/Julia).
Gracias a los lectores que señalaron estas dos lagunas.
++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++
La publicación está incompleta sin mencionar dos enlaces.
1. Aashish cubrió la buena teoría detrás del algoritmo líder del ciclo. Vea su publicación sobre la transformación de strings .
2. Como de costumbre, Sambasiva demostró sus habilidades excepcionales en la recursión al problema . Asegúrese de entender su solución.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA