Separación estable para dos clases de elementos en una matriz

Considere el siguiente problema.Separación estable para dos clases de elementos en una matriz

Nos dan una serie de elementos que pertenecen a una dos clases: ya sea rojo o azul. Tenemos que reorganizar los elementos de la matriz para que todos los elementos azules sean los primeros (y todos los elementos rojos siguen). La reorganización debe hacerse de manera estable, lo que significa que se debe preservar el orden relativo de los elementos azules (lo mismo para los rojos).

¿Hay algún algoritmo inteligente que realice la reordenación anterior en su lugar?

Una solución in situ es, por supuesto, sencilla.

Una solución obvia en el lugar sería aplicar cualquier algoritmo de clasificación estable a la matriz. Sin embargo, usar un algoritmo de clasificación completo en una matriz se siente intuitivamente como una exageración, especialmente teniendo en cuenta el hecho de que solo estamos tratando con dos clases de elementos.

Cualquier idea muy apreciada.

Fuente

2010-05-25 AnT

Es posible hacerlo en O (n) tiempo y O (1) espacio aparentemente. El documento Stable minimum space partitioning in linear time de Jyrki Katajainen, y Tomi Pasanen afirma que puede hacerlo.

Google para estable 0-1 clasificación.

Fuente

2010-05-25 17:38:08

Gracias. Lamentablemente, el artículo solo está disponible por suscripción, pero al menos ahora sé que es 1) posible, 2) no trivial :) – AnT

Está disponible de forma gratuita en CiteSeer: http://citeseerx.ist.psu.edu/ viewdoc/summary? doi = 10.1.1.25.5554 –

@Ants Aasma: Gracias por el enlace. He actualizado la respuesta con eso. –

No conozco el algoritmo O (n) pero aquí hay un algoritmo simple con complejidad O (n * log (n)) en el peor de los casos. Tal vez será útil.

Cortar los ceros desde el principio y desde el final, ya están en su lugar. Ahora la matriz se ve como una secuencia de unos seguidos de una secuencia de ceros seguida por una secuencia de unos y así, 1010101010

Intercambia la primera secuencia de unos con la primera secuencia de ceros, la tercera secuencia de unos con la tercera secuencia de ceros, etc. Se convertirá en: 0110011001

La cantidad de secuencias se convirtió en aproximadamente dos veces menos. Repita el procedimiento anterior hasta que la matriz esté ordenada.

Para intercambiar dos secuencias contiguas, invierta la primera, luego la segunda, y luego invierta ambas.

Fuente

2010-05-25 19:58:42 rem

Esto es O (n^2) en el peor de los casos: considere 0 1 (n/2 veces) 0 1 0 1 ... 0 1. Una solución O (nlogn) simple debe tener una función de comparación lexicográfica (color , index) y usa cualquier método de clasificación usando esa función de comparación. –

No, la cantidad de pases es O (log (n)) en el peor de los casos. Aquí hay un ejemplo: http://pastebin.com/NyekVWmv – rem

No existe un algoritmo de clasificación O (n * log (n)) estable en el lugar. Por lo general, la clasificación estable en diferentes bibliotecas se implementa mediante la combinación de clasificación que requiere O (n) memoria adicional, véase, por ejemplo, la implementación de GNU C++ de stable_sort y Arrays.sort de Sun Java. – rem

Esto se llama Particionamiento estable en C++ y hay un algoritmo estándar para esto: std::stable_partition.

La implementación SGI tiene un comportamiento de adaptación en función de la cantidad de memoria disponible:

se ejecuta en O (N) si es posible asignar O (N) espacio
se ejecuta en O (N log N) swaps en el lugar

Me pregunto si la solución de este último en el lugar utiliza un algoritmo de clasificación estable detrás de las escenas.

Fuente

2010-05-26 07:21:46

Separación estable para dos clases de elementos en una matriz

Respuesta

Cuestiones relacionadas