c++ - soluciones - ¿Desentregar una matriz en su lugar?

matriz caida soluciones

Question

Digamos que tengo una matriz de datos entrelazados, como 1a2b3c4d5e, y quiero desentrelazarlos en una matriz que parece 12345abcde, en su lugar (sin un búfer temporal). ¿Cuál sería la forma más rápida de hacer esto?

Lo que tengo hasta ahora es esto

template<typename T>
void deinterlace(T* arr, int length){
  if(length<=1) return;

  int i = 1;
  for(i = 1; i*2<length; i++){
    //swap i with i*2
    T temp = arr[i];
    arr[i] = arr[i*2];
    arr[i*2] = temp;
  }
  deinterlace(arr+i, length-i);
}

que desafortunadamente no funciona con matrices, no una potencia de 2 en tamaño

edición : este algo falla a potencias mayores de 2 de todos modos, así que supongo que estoy en el cuadrado 0 otra vez

edición 2 : he encontrado un algoritmo nlogn para esto, dada una función de rotación de matriz O (n) o un tamaño inicial que es una potencia de 2

Funciona así

1a2b3c4d5e6f7g, "tamaño de fragmento" = 1 inicial,

dividir en grupos de tamaño de trozo * 4 1a2b 3c4d 5e6f 7g

intercambie los 2 pedazos internos de cada grupo 12ab 34cd 56ef 7g

repetir con tamaño de trozo = tamaño de trozo * 2

12ab34cd 56ef7g (lea: 56 ef 7 g) -> 1234abcd 567efg

1234abcd567efg -> 1234567abcdefg

template<typename T>
void deinterlace(T* arr, int length, int group_ct = 1){
  if(group_ct*2 >= length) return;

  for(int i = 0; i<length; i+=group_ct*4){
    int rot_count = group_ct;

    int i1 = i + group_ct;
    int i2 = i+group_ct*4 - group_ct;

    if(i2+group_ct > length){
      i2 = i1 + (length-i1)/2+group_ct/2;
    }

    rotate(arr, i1, i2, group_ct);

  }

  deinterlace(arr, length, group_ct * 2);
}

edición 3 Supongo que el término correcto es desentrelazar, no desentrelazar

Answer 1

Esto es esencialmente un problema de transposición matricial. Tu matriz

[1 a]
[2 b]
[3 c]
[4 d]

es equivalente a 1, a, 2, b, 3, c, 4, d si se representa como un vector (leyendo primero las filas). La transposición de esta matriz es:

[1 2 3 4]
[a b c d]

que es equivalente a 1, 2, 3, 4, a, b, c, d .

Hay una página de wikipedia que trata sobre la transposición de la matriz en el lugar para los casos generales. Supongo que el algoritmo para la matriz no cuadrada sería directamente aplicable.

Hay un algoritmo lento (no estoy seguro si O (n ^ 2) o peor, y es tarde) que puedes usar. La idea es rotar en su lugar la sub-matriz de la posición i a la posición 2*i . Por ejemplo:

START: 1a2b3c4d5e6f
1(a2)...         -> 1(2a)...
12(ab3)...       -> 12(3ab)...
123(abc4)...     -> 123(4abc)...
1234(abcd5)...   -> 1234(5abcd)...
12345(abcde6)... -> 12345(6abcde)..
123456(abcdef)   -> DONE

El primer miembro de la matriz es el índice 0. En el paso 1, selecciona la sub-matriz a[1:2] , y la gira hacia la derecha (todos los miembros van a la siguiente ubicación, y la última va al inicio). En el siguiente paso, seleccione a[2:4] y gírelo, etc. Asegúrese de no rotar la última sub-matriz a[n/2:n] .

Y una opción final, si no necesita realizar operaciones masivas para el rendimiento (como memcpy ), es proporcionar una función de acceso y transformar el índice en lugar de mover cualquier byte. Dicha función es casi trivial de escribir: si el índice es menor que max/2 , devuelva la entrada a 2*index ; de lo contrario, devuelva la entrada a 2*(index-max/2)+1 .

Answer 2

Si no te importa el orden de la matriz resultante, la forma más rápida que se me ocurre es hacer swaps sucesivos utilizando un índice ''cabeza'' y ''cola''.

int head = 1;
int tail = length - 2;
while (head < tail)
{
    T temp = arr[head];
    temp = arr[head];
    arr[head] = arr[tail];
    arr[tail] = temp;
    head += 2;
    tail -= 2;
}

Para su caso de ejemplo, el resultado sería 15243cbdae después de 2 iteraciones.

Answer 3

Su idea original casi funcionará para un desentrelazado en el lugar. Solo debe tener en cuenta el hecho de que cuando intercambia un elemento en su lugar, desplaza el elemento que la fórmula espera encontrar allí.

Entonces, primero, defina la función source_index : dada una matriz perfectamente intercalada de longitud N y un índice i , devuelva el elemento que debería estar en i . La primera mitad proviene de todos los demás elementos pares, la última mitad de todos los demás elementos impares.

int source_index(int i, int length) {
  int mid = length-length/2;

  if (i<mid) {
    return i*2;
  }
  return (i-mid)*2+1;
}

Ahora puedes caminar a través de la matriz cambiando elementos en su lugar. Pero si encuentra un índice de origen que es menor que el índice objetivo actual, debe volver a realizar el cálculo para averiguar dónde se intercambió.

template<typename T>
void deinterlace(T* arr, int length){
  if(length<=1) return;

  int i = 1;
  for(i = 1; i<length; i++){
    int j = next_index(i, length);
    while (j<i) { //walk the chain of swaps
      j = next_index(j, length);
     }
    T temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Esto hace exactamente N swaps. El número de llamadas a next_index es algo caótico, pero parece mostrar un crecimiento de NlgN.