algorithm - resueltos - Permutación probablemente correcta en menos de O(n ^ 2)

permutaciones ejemplos

Question

Escrito en Haskell, aquí está el tipo de datos que prueba que una lista es una permutación de otra:

data Belongs (x :: k) (ys :: [k]) (zs :: [k]) where
  BelongsHere :: Belongs x xs (x '': xs)
  BelongsThere :: Belongs x xs xys -> Belongs x (y '': xs) (y '': xys)

data Permutation (xs :: [k]) (ys :: [k]) where
  PermutationEmpty :: Permutation ''[] ''[]
  PermutationCons :: Belongs x ys xys -> Permutation xs ys -> Permutation (x '': xs) xys

Con una Permutation , ahora podemos permutar un registro:

data Rec :: (u -> *) -> [u] -> * where
  RNil :: Rec f ''[]
  (:&) :: !(f r) -> !(Rec f rs) -> Rec f (r '': rs)

insertRecord :: Belongs x ys zs -> f x -> Rec f ys -> Rec f zs
insertRecord BelongsHere v rs = v :& rs
insertRecord (BelongsThere b) v (r :& rs) = r :& insertRecord b v rs

permute :: Permutation xs ys -> Rec f xs -> Rec f ys
permute PermutationEmpty RNil = RNil
permute (PermutationCons b pnext) (r :& rs) = insertRecord b r (permute pnext rs)

Esto funciona bien. Sin embargo, el permuto es O(n^2) donde n es la longitud del registro. Me pregunto si hay una manera de hacerlo más rápido utilizando un tipo de datos diferente para representar una permutación.

A modo de comparación, en una configuración mutable y sin tipo (que sé que es una configuración muy diferente), podríamos aplicar una permutación a un registro heterogéneo como este en tiempo O(n) . Usted representa el registro como una matriz de valores y la permutación como una matriz de nuevas posiciones (no se permiten duplicados y todos los dígitos deben estar entre 0 y n). Aplicar la permutación es solo iterar esa matriz e indexar en la matriz del registro con esas posiciones.

No espero que sea posible una permutación O(n) en una configuración más rigurosa. Pero parece que O(n*log(n)) podría ser posible. Aprecio cualquier comentario y quiero saber si necesito aclarar algo. Además, las respuestas a esto pueden usar Haskell, Agda o Idris dependiendo de lo que se sienta más fácil para comunicarse.

Answer 1

Una solución simple más rápida es comparar la permutación ordenada de las permutaciones.

1. Dada permutación A y B.

2. Luego existen las permutaciones ordenadas,

   As = sort (A) Bs = sort (B)

3. Como es una permutación de A y Bs es una permutación de B.

4. Si As == Bs, entonces A es una permutación de B.

Por lo tanto, el orden de este algoritmo es O (n log (n)) <O (n²)

Y esto está llevando a la solución óptima.

Usando un almacenamiento diferente de los rendimientos de permutación O (n)

Usando las declaraciones de arriba, estamos cambiando el formato de almacenamiento de cada permutación a

• los datos ordenados
• los datos originales sin clasificar

Para determinar si una lista es una permutación de otra, es necesaria una comparación simple de los datos ordenados -> O (n).

Esto responde a la pregunta correctamente, pero el esfuerzo está oculto al crear el almacenamiento de datos duplicado ^^ Por lo tanto, dependerá del uso si esto es una ventaja real o no.