algorithm - soluciones - reposo despues de sobar la matriz

¿Es posible reorganizar una matriz en su lugar en O(N)?

Question

Si tengo una matriz de objetos de tamaño N, y tengo una matriz de números únicos en el rango 1 ... N, ¿existe algún algoritmo para reorganizar la matriz de objetos en el lugar especificado en la lista de números, y sin embargo, hacer esto en tiempo O (N)?

Contexto: estoy haciendo un algoritmo de clasificación rápida en objetos que son bastante grandes en tamaño, por lo que sería más rápido realizar los intercambios en índices que en los objetos en sí, y solo mover los objetos en una pasada final. Solo me gustaría saber si podría hacer esta última pasada sin asignar memoria para una matriz separada.

Edit: No estoy preguntando cómo hacer una ordenación en tiempo O (N), sino cómo hacer la reorganización posterior a la ordenación en tiempo O (N) con espacio O (1). Lo siento por no dejar esto claro.

Answer 1

¿Quiere decir que tiene una matriz de objetos O [1..N] y luego tiene una matriz P [1..N] que contiene una permutación de números 1..N y al final desea obtener una matriz O1 de objetos tales que O1 [k] = O [P [k]] para todos k = 1..N?

Como ejemplo, si sus objetos son las letras A, B, C ..., Y, Z y su matriz P es [26,25,24, .., 2,1] es la salida deseada Z, Y, .. .C, B, A?

En caso afirmativo, creo que puede hacerlo en tiempo lineal utilizando solo memoria adicional O (1). Revertir elementos de una matriz es un caso especial de este escenario. En general, creo que debería considerar la descomposición de su permutación P en ciclos y luego usarla para moverse alrededor de los elementos de su matriz original O [].

Si eso es lo que buscas, puedo elaborar más.

EDITAR: Otros ya presentaron excelentes soluciones mientras dormía, así que no es necesario repetirlo aquí. ^ _ ^

EDITAR: Mi O (1) espacio adicional no es del todo correcto. Estaba pensando solo en los elementos de "datos", pero en realidad también necesita almacenar un bit por elemento de permutación, por lo que si somos precisos, necesitamos O (log n) bits adicionales para eso. Pero la mayoría de las veces usar un bit de signo (como lo sugiere JF Sebastian) está bien, por lo que en la práctica es posible que no necesitemos más de lo que ya tenemos.

Answer 2

Creo que esto debería hacer:

static <T> void arrange(T[] data, int[] p) {
    boolean[] done = new boolean[p.length];        
    for (int i = 0; i < p.length; i++) {
        if (!done[i]) {
            T t = data[i];
            for (int j = i;;) {
                done[j] = true;

                if (p[j] != i) {
                    data[j] = data[p[j]];
                    j = p[j];
                } else {
                    data[j] = t;
                    break;
                }
            }                
        }
    }
}

Nota: Esto es Java. Si lo hace en un idioma sin recolección de basura, asegúrese de eliminar el done .

Si te importa el espacio, puedes usar un BitSet para done . Supongo que puede permitirse un bit adicional por elemento porque parece estar dispuesto a trabajar con una matriz de permutación, que es varias veces ese tamaño.

Este algoritmo copia instancias de Tn + k veces, donde k es el número de ciclos en la permutación. Puede reducir esto al número óptimo de copias omitiendo aquellas i donde p [i] = i.

Answer 3

El enfoque es seguir los "ciclos de permutación" de la permutación, en lugar de indexar la matriz de izquierda a derecha. Pero como tiene que comenzar en algún lugar, cada vez que se necesita un nuevo ciclo de permutación, la búsqueda de elementos no permitidos es de izquierda a derecha:

// Pseudo-code N : integer, N > 0 // N is the number of elements swaps : integer [0..N] data[N] : array of object permute[N] : array of integer [-1..N] denoting permutation (used element is -1) next_scan_start : integer;
next_scan_start = 0;
while (swaps < N ) { // Search for the next index that is not-yet-permtued. for (idx_cycle_search = next_scan_start; idx_cycle_search < N; ++ idx_cycle_search) if (permute[idx_cycle_search] >= 0) break;
next_scan_start = idx_cycle_search + 1;
// This is a provable invariant. In short, number of non-negative // elements in permute[] equals (N - swaps) assert( idx_cycle_search < N );
// Completely permute one permutation cycle, ''following the // permutation cycle''s trail'' This is O(N) while (permute[idx_cycle_search] >= 0) { swap( data[idx_cycle_search], data[permute[idx_cycle_search] ) swaps ++; old_idx = idx_cycle_search; idx_cycle_search = permute[idx_cycle_search]; permute[old_idx] = -1; // Also ''= -idx_cycle_search -1'' could be used rather than ''-1'' // and would allow reversal of these changes to permute[] array } }

Answer 4

El problema consiste en aplicar una permutación en su lugar con un mínimo de almacenamiento adicional de O (1): "permutación in situ".

Es solucionable, pero un algoritmo no es obvio de antemano.

Se describe brevemente como un ejercicio en Knuth, y para el trabajo tuve que descifrarlo y descubrir cómo funcionaba. Mira el 5.2 # 13.

Para un trabajo más moderno sobre este problema, con pseudocódigo:

http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/forschung/berichte/bericht_273.pdf

Answer 5

Hay una clasificación de histograma , aunque el tiempo de ejecución se da un poco más alto que O (N) (N log log n).

Answer 6

Puedo hacerlo dado O (N) espacio de scratch: copiar en una nueva matriz y volver a copiar.

EDITAR: Soy consciente de la existencia de un algoritmo que seguirá adelante. La idea es realizar los intercambios en la matriz de enteros 1..N mientras que al mismo tiempo reflejar los intercambios en su matriz de objetos grandes. Simplemente no puedo encontrar el algoritmo en este momento.

Answer 7

Si no le importó asignar memoria para un hash adicional de índices, puede mantener una asignación de la ubicación original a la ubicación actual para obtener una complejidad de tiempo cercana a O (n). Aquí hay un ejemplo en Ruby, ya que es legible y seudocódigo-ish. (Esto podría ser más corto o más idiomáticamente Ruby-ish, pero lo he escrito para mayor claridad).

#!/usr/bin/ruby

objects       = [''d'', ''e'', ''a'', ''c'', ''b'']
order         = [2, 4, 3, 0, 1]
cur_locations = {}

order.each_with_index do |orig_location, ordinality|
  # Find the current location of the item.
  cur_location = orig_location
  while not cur_locations[cur_location].nil? do
    cur_location = cur_locations[cur_location]
  end

  # Swap the items and keep track of whatever we swapped forward.
  objects[ordinality], objects[cur_location] = objects[cur_location], objects[ordinality]
  cur_locations[ordinality] = orig_location
end

puts objects.join('' '')

Obviamente, esto implica algo de memoria adicional para el hash, pero como es solo para los índices y no para los objetos "bastante grandes", es de esperar que sea aceptable. Dado que las búsquedas de hash son O (1), aunque hay un ligero aumento en la complejidad debido al caso en el que un elemento se ha cambiado hacia adelante más de una vez y tiene que volver a escribir cur_location varias veces, el algoritmo en su conjunto debe ser razonablemente cerca de O (n).

Si quisiera, podría crear un hash completo del original a las posiciones actuales con anticipación, o mantener un hash inverso de la corriente al original, y modificar el algoritmo un poco para reducirlo a O (n) estrictamente. Sería un poco más complicado y tomaría un poco más de espacio, por lo que esta es la versión que escribí, pero las modificaciones no deberían ser difíciles.

EDITAR: En realidad, estoy bastante seguro de que la complejidad del tiempo es solo O (n), ya que cada ordinalidad puede tener como máximo un salto asociado y, por lo tanto, el número máximo de búsquedas se limita a n.

Answer 8

Terminé escribiendo un algoritmo diferente para esto, que primero genera una lista de swaps para aplicar un pedido y luego ejecuta los swaps para aplicarlo. La ventaja es que si está aplicando el pedido a varias listas, puede reutilizar la lista de swaps, ya que el algoritmo de swap es extremadamente simple.

void make_swaps(vector<int> order, vector<pair<int,int>> &swaps)
{
    // order[0] is the index in the old list of the new list''s first value.
    // Invert the mapping: inverse[0] is the index in the new list of the
    // old list''s first value.
    vector<int> inverse(order.size());
    for(int i = 0; i < order.size(); ++i)
        inverse[order[i]] = i;

    swaps.resize(0);

    for(int idx1 = 0; idx1 < order.size(); ++idx1)
    {
        // Swap list[idx] with list[order[idx]], and record this swap.
        int idx2 = order[idx1];
        if(idx1 == idx2)
            continue;

        swaps.push_back(make_pair(idx1, idx2));

        // list[idx1] is now in the correct place, but whoever wanted the value we moved out
        // of idx2 now needs to look in its new position.
        int idx1_dep = inverse[idx1];
        order[idx1_dep] = idx2;
        inverse[idx2] = idx1_dep;
    }
}

template<typename T>
void run_swaps(T data, const vector<pair<int,int>> &swaps)
{
    for(const auto &s: swaps)
    {
        int src = s.first;
        int dst = s.second;
        swap(data[src], data[dst]);
    }
}

void test()
{
    vector<int> order = { 2, 3, 1, 4, 0 };

    vector<pair<int,int>> swaps;
    make_swaps(order, swaps);

    vector<string> data = { "a", "b", "c", "d", "e" };
    run_swaps(data, swaps);
}

Answer 9

#!/usr/bin/env python

def rearrange(objects, permutation):
    """Rearrange `objects` inplace according to `permutation`.

       ``result = [objects[p] for p in permutation]``
    """
    seen = [False] * len(permutation)
    for i, already_seen in enumerate(seen):
        if not already_seen: # start permutation cycle
            first_obj, j = objects[i], i
            while True:
                seen[j] = True
                p = permutation[j]
                if p == i: # end permutation cycle
                    objects[j] = first_obj    # [old] p -> j
                    break
                objects[j], j = objects[p], p #       p -> j

El algoritmo (como he notado después de que lo escribí) es el mismo que el de la respuesta de @meriton en Java .

Aquí hay una función de test para el código:

def test():
    import itertools
    N = 9
    for perm in itertools.permutations(range(N)):
        L = range(N)
        LL = L[:]
        rearrange(L, perm)
        assert L == [LL[i] for i in perm] == list(perm), (L, list(perm), LL)

    # test whether assertions are enabled
    try:
        assert 0
    except AssertionError:
        pass
    else:
        raise RuntimeError("assertions must be enabled for the test")

if __name__ == "__main__":
    test()