¿Hay dos matrices de permutación entre sí?

Question

Duplicar posible:
Check if array B is a permutation of A

dieron 2 matrices de enteros sin clasificar a y b de igual tamaño. Determine si b es una permutación de a. ¿Se puede hacer esto en O(n) time y O(1) space?

La primera solución que me vino a la mente es que está usando XOR, es decir, XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a. Pero da ejemplos donde este enfoque falla. Para por ejemplo -

a: [1 6 0 0 4] -- b: [1 0 6 1 5] 
a: [1 6 0 0 5] -- b: [1 0 6 1 4] 

Cualquiera que tenga alguna idea, que la forma de hacerlo en O(n) time y O(1) space?

Answer 1

Si los elementos de ajuste no son negativos, y usted tiene un tipo entero sin límites (una BigInteger o similar) disponibles, se podría definir una función sobre un conjunto A:

C(A) = product(p_(a+1))) para cada a en A

donde p_n es el n número primo th. Entonces C depende solamente de los valores en A, en lugar de su orden; y cualquier cambio en los valores cambia C.

Por ejemplo,

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244 

(y, obviamente, cualquier conjunto con los mismos elementos tiene la misma C, cualquiera que sea el orden), y

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366 

por lo que sabemos estos conjuntos son diferentes. Utiliza el teorema fundamental de la aritmética que establece que cualquier entero mayor que 1 se puede escribir como un producto único (hasta el orden de los factores) de los números primos. O tal vez usa un corolario. Acabo de crear este método, por lo que podría no funcionar. Este post no es un intento de una prueba de su corrección ...

Answer 2

En el caso de una gama limitada de números enteros - deje que la gama sea tal que [n,m]m-n = U puede ordenar las matrices usando in place radix sort, también se discutió en this great post.

Después de tener dos matrices ordenadas, una iteración simple en ambas puede dar la respuesta, las matrices originales son permutaciones entre sí, si y solo si las matrices ordenadas son idénticas.

Nota:
hay algo de "trampa" en esta respuesta [por lo tanto yo no publicar hasta que el PO pidió en los comentarios ..], ya que la complejidad del tiempo es O(nlogU), y el espacio es O(logU). Sin embargo, para rangos acotados, podemos suponer O(logU) = O(1), y para estos casos obtenemos O(n) de tiempo y O(1) de espacio.

Answer 3

Su solución OR exclusivo es básicamente una solución basada en hash, pero con una función hash de baja calidad.

Lo que queremos es una función hash que ...

1. Da hashes que son extremadamente poco probable que chocan, para que puedan ser tratados como identificadores únicos para los números enteros. Git usa hashes SHA-1 para identificar versiones de código fuente, con una probabilidad de colisión tan baja que puede ser ignorada.

2. Conmutativo (como xor y plus) y probablemente asociativo, por lo que el orden de los elementos no cambia el hash resultante.

Ese segundo requisito es probablemente el incómodo. Pasé un poco de tiempo en Google, pero me asusté de palabras como "Quasigroup".