¿Buena función hash para permutaciones?

Question

Tengo números en un rango específico (generalmente de 0 a alrededor de 1000). Un algoritmo selecciona algunos números de este rango (de 3 a 10 números). Esta selección se realiza con bastante frecuencia, y necesito verificar si ya se ha seleccionado una permutación de los números elegidos.

por ejemplo, un paso selecciona [1, 10, 3, 18] y otro [10, 18, 3, 1], entonces la segunda selección se puede descartar porque es una permutación.

Necesito hacer este control muy rápido. Ahora pongo todas las matrices en un hashmap y uso una función hash personalizada: simplemente resume todos los elementos, por lo que 1 + 10 + 3 + 18 = 32, y también 10 + 18 + 3 + 1 = 32. Para iguales, utilizo un conjunto de bits para verificar rápidamente si los elementos están en ambos conjuntos (no necesito clasificación cuando uso el conjunto de bits, pero solo funciona cuando el rango de números es conocido y no demasiado grande).

Esto funciona bien, pero puede generar muchas colisiones, por lo que el método equals() se llama con bastante frecuencia. Me preguntaba si hay una manera más rápida de buscar permutaciones.

¿Hay buenas funciones hash para las permutaciones?

ACTUALIZACIÓN

he hecho un poco de referencia: generar todas las combinaciones de números en el rango de 0 a 6, y longitud de la matriz 1 a 9. Hay 3003 permutaciones posibles, y una buena de hash debe generado cerca a esto muchas diferentes hashes (que usar números de 32 bits para el hash):

hashes

• 41 diferentes sólo por la adición de (así que hay un montón de colisiones)
• 8 hashes diferentes valores para XOR'ing juntos
• 286 hashes diferentes para multiplicar
• 3003 hashes diferentes para (I + 2e) y multiplicando como ABC ha sugerido (usando 1779033703 para R)

Así hash del ABC se puede calcular muy rápido y es mucho mejor que todo el resto. ¡Gracias!

PD: No quiero ordenar los valores cuando no es necesario, porque esto sería demasiado lento.

Answer 1

Un candidato potencial podría ser esto. Repare un entero impar R. Para cada elemento e usted quiere calcular el factor hash (R + 2 * e). Luego calcule el producto de todos estos factores. Finalmente divida el producto por 2 para obtener el hash.

El factor de 2 en (R + 2e) garantiza que todos los factores son impares, por lo tanto evitando que el producto siempre convertirse en 0. La división por 2 en el extremo es porque el producto será siempre impar, de ahí el La división simplemente elimina un bit constante.

E.g. Elijo R = 1779033703. Esta es una elección arbitraria, hacer algunos experimentos debería mostrar si un R dado es bueno o malo. Suponga que sus valores son [1, 10, 3, 18]. El producto (calculado utilizando enteros de 32 bits) es

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 

Por lo tanto el hash habría

3376724311/2 = 1688362155.

Answer 2

Sumar los elementos ya es una de las cosas más simples que puede hacer. Pero no creo que sea una función de hash particularmente buena w.r.t. pseudo aleatoriedad.

Si ordena sus matrices antes de almacenarlas o hash de cálculo, todas las funciones de hash funcionarán bien.

Si se trata de velocidad: ¿Ha medido dónde está el cuello de botella? Si su función hash le está causando muchas colisiones y tiene que pasar la mayor parte del tiempo comparando las matrices bit por bit, la función hash obviamente no es buena en lo que se supone que debe hacer. Sorting + Better Hash podría ser la solución.

Answer 3

dependiendo de si tiene muchas colisiones (por lo tanto, el mismo hash pero no una permutación), puede preseleccionar las matrices al tiempo que las mezcla. En ese caso puedes hacer un hashing más agresivo donde no solo sumas los números sino que también le agregas bitmagick para obtener hashes bastante diferentes.

Esto solo es beneficioso si recibe muchas colisiones no deseadas porque el hash que está haciendo ahora es demasiado pobre.Si apenas tiene colisiones, el método que está utilizando parece correcto

Answer 4

Me gusta usar el código hash predeterminado de la cadena (Java, C# no estoy seguro acerca de otros lenguajes), genera códigos hash bastante únicos. así que si primero ordena la matriz, y luego genera una cadena única usando algún delimitador.

por lo que se puede hacer lo siguiente (Java):

int[] arr = selectRandomNumbers(); 
    Arrays.sort(arr); 
    int hash = (arr[0] + "," + arr[1] + "," + arr[2] + "," + arr[3]).hashCode(); 

si el rendimiento es un problema, se puede cambiar la concatenación de cadenas ineficiente sugerido usar StringBuilder o String.Format

String.format("{0},{1},{2},{3}", arr[0],arr[1],arr[2],arr[3]); 

Cadena Por supuesto, el código hash no garantiza que dos cadenas distintas tengan hash diferente, pero teniendo en cuenta este formato sugerido, las colisiones deberían ser extremadamente raras.

Answer 5

sugeriría esto: 1. Comprobar si las longitudes de permutaciones son los mismos (si no - no son iguales)

2. Ordernar 1 matriz. En lugar de ordenar otra matriz, itere a través de los elementos de la 1ra matriz y busque la presencia de cada una de ellas en la segunda matriz (compárelo solo mientras los elementos en la 2da matriz sean más pequeños, no itere a través de toda la matriz).

nota: si puede tener los mismos números en sus permutaciones (ej. [1,2,2,10]), entonces necesitará eliminar elementos de la 2 ª serie cuando coincida con un miembro de la 1ra. .

pseudo-código:

if length(arr1) <> length(arr2) return false; 
sort(arr2); 
for i=1 to length(arr1) { 
elem=arr1[i]; 
j=1; 
while (j<=length(arr2) and elem<arr2[j]) j=j+1; 
if elem <> arr2[j] return false; 
} 
return true; 

la idea es que en lugar de ordenar otra matriz podemos sólo tratar de coincidir con todos sus elementos en el arreglo ordenado.

Answer 6

Probablemente pueda reducir mucho las colisiones utilizando el producto y la suma de los términos.

1 * 10 * 3 * 18 = 540 y 10 * 18 * 3 * 1 = 540

por lo que el hash de suma-producto sería [32540]

usted todavía tiene que hacer algo acerca de las colisiones cuando suceden aunque

Answer 7

Si entiendo bien su pregunta que desee para probar la igualdad entre los conjuntos donde los artículos no están ordenados. Esto es precisamente lo que un filtro Bloom hará por usted. A expensas de una pequeña cantidad de falsos positivos (en cuyo caso deberá realizar una llamada a una comparación de conjuntos de fuerza bruta) podrá comparar dichos conjuntos al verificar si su hash de filtro Bloom es igual.

La razón algebraica por la que esto sucede es que la operación OR es conmutativa. Esto también se aplica a otros semirremolques.