¿Suma de comprobación para una matriz de enteros?

Question

Tengo una matriz que es de tamaño 4,9,16 o 25 (según la entrada) y los números en la matriz son los mismos pero menos en uno (si el tamaño de la matriz es 9 entonces el elemento más grande en la matriz sería 8) los números comienzan con 0 y me gustaría hacer algún algoritmo para generar algún tipo de suma de comprobación para la matriz, de forma que pueda comparar que 2 matrices son iguales sin recorrer toda la matriz y verificar cada elemento uno a uno.

¿Dónde puedo obtener este tipo de información? Necesito algo que sea lo más simple posible. Gracias.

edición: sólo para estar claro en lo que quiero:

-Todos los números de la matriz son distintos, por lo que [0,1,1,2] no es válida porque hay un elemento repetido (1)

-La posición de la materia números, por lo [0,1,2,3] no es el mismo que [3,2,1,0]

-La matriz contendrá el número 0, por lo que esto también debe tenerse en cuenta.

EDIT:

bien he tratado de aplicar el algoritmo de Fletcher aquí: http://en.wikipedia.org/wiki/Fletcher%27s_checksum#Straightforward

int fletcher(int array[], int size){ 
    int i; 
    int sum1=0; 
    int sum2=0; 
    for(i=0;i<size;i++){ 
    sum1=(sum1+array[i])%255; 
    sum2=(sum2+sum1)%255; 
    } 
    return (sum2 << 8) | sum1; 
} 

para ser honesto no tengo idea de lo que hace la línea de retorno de hacer, pero por desgracia, el algoritmo no funciona . Para las matrices [2,1,3,0] y [1,3,2,0] obtengo la misma suma de comprobación.

Edit2:

bien aquí está otro, la suma de comprobación Adler http://en.wikipedia.org/wiki/Adler-32#Example_implementation

#define MOD 65521; 

unsigned long adler(int array[], int size){ 
    int i; 
    unsigned long a=1; 
    unsigned long b=0; 
    for(i=0;i<size;i++){ 
    a=(a+array[i])%MOD; 
    b=(b+a)%MOD; 
    } 
    return (b <<16) | a; 
} 

Esto también no funciona. Las matrices [2,0,3,1] y [1,3,0,2] generan la misma suma de comprobación. Estoy perdiendo la esperanza aquí, ¿alguna idea?

Answer 1

Tomemos el caso de su matriz de 25 enteros. Usted explica que puede contener permutaciones de los enteros únicos de 0 a 24. De acuerdo con this page, ¡hay 25! (25 factoriales) posibles permutaciones, es decir 15511210043330985984000000. Puede contener mucho más que un entero de 32 bits.

La conclusión es que tendrá una colisión, sin importar cuánto lo intente.

Ahora, aquí es un simple algoritmo que dan cuenta de la posición:

int checksum(int[] array, int size) { 
    int c = 0; 
    for(int i = 0; i < size; i++) { 
    c += array[i]; 
    c = c << 3 | c >> (32 - 3); // rotate a little 
    c ^= 0xFFFFFFFF; // invert just for fun 
    } 
    return c; 
} 

Answer 2

Para una matriz de N enteros únicos de 1 a N, solo sumando los elementos siempre será N * (N + 1)/2. Por lo tanto, la única diferencia está en el orden. Si por "suma de verificación" implica que tolera algunas colisiones, una forma es sumar las diferencias entre números consecutivos. Entonces, por ejemplo, la suma de comprobación delta para {1,2,3,4} es 1 + 1 + 1 = 3, pero la suma de comprobación delta para {4,3,2,1} es -1 + -1 + -1 = -3. se les dio

No hay requisitos para las tasas de colisión o de la complejidad computacional, pero si lo anterior no le conviene, entonces me recomiendan un position dependent checksum

Answer 3

Creo que lo que quiere es en la respuesta del siguiente hilo:

Fast permutation -> number -> permutation mapping algorithms

Simplemente tome el número al que está asignada su permutación y tómela como su suma de comprobación. Como hay exactamente una suma de comprobación por permutación, no puede haber una suma de comprobación más pequeña sin colisión.

Answer 4

Por lo que entiendo, su matriz contiene una permutación de números del 0 al N-1. Una suma de verificación que será útil es el rango de la matriz en su orden lexicográfico. Qué significa ?Dada 0, 1, 2 Tiene las posibles permutaciones

1: 0, 1, 2 
    2: 0, 2, 1 
    3: 1, 0, 2 
    4: 1, 2, 0 
    5: 2, 0, 1 
    6: 2, 1, 0 

La comprobación de suma será el primer número, y se calcula cuando se crea la matriz. Hay soluciones propuestas en

Find the index of a given permutation in the list of permutations in lexicographic order

que puede ser útil, aunque parece el mejor algoritmo era de complejidad cuadrática. Para mejorarlo a la complejidad lineal, debe almacenar en antememoria los valores de los factoriales.

¿La ventaja? CERO colisión

EDIT: Computación El valor es como la evaluación de un polinomio, donde se utiliza factorial para el monomio en lugar de poder. Por lo que la función es

f(x0,....,xn-1) = X0 * (0!) + X1 * (1!) + X2 * (2!) +...+ Xn-1 * (n-1!) 

La idea es utilizar cada uno valores para obtener una sub-serie de permutaciones, y con valores suficientes a identificar una permutación única.

Ahora para la aplicación (como la de un polinomio):

1. pre cálculo 0 .... a n-1! al comienzo del programa
2. Cada vez que se establece una matriz que utiliza f (elementos) para calcular la suma de comprobación
3. se compara en O (1) el uso de esta suma de comprobación

Answer 5

¿Qué hay de la suma de comprobación de la suma ponderada? Tomemos un ejemplo para [0,1,2,3]. Primero elige una semilla y el límite, vamos a elegir una semilla como el 7 y el límite como 10000007.

a[4] = {0, 1, 2, 3} 
limit = 10000007, seed = 7 
result = 0 
result = ((result + a[0]) * seed) % limit = ((0 + 0) * 7)) % 10000007 = 0 
result = ((result + a[1]) * seed) % limit = ((0 + 1) * 7)) % 10000007 = 7 
result = ((result + a[2]) * seed) % limit = ((7 + 2) * 7)) % 10000007 = 63 
result = ((result + a[3]) * seed) % limit = ((63 + 3) * 7)) % 10000007 = 462 

Su control es 462 para que [0, 1, 2, 3]. La referencia es http://www.codeabbey.com/index/wiki/checksum