정수 배열의 체크섬?

Question

크기가 4,9,16 또는 25 인 배열 (입력에 따라 다름)과 배열의 숫자가 같지만 하나씩 작습니다 (배열 크기가 9 인 경우 배열의 가장 큰 요소 인 경우). 8이 될 것입니다 숫자가 0으로 시작 및 배열에 대한 체크섬의 일종을 생성 할 수 있도록 몇 가지 알고리즘을 수행 할 수 있도록 2 배열은 전체 배열을 통해 반복 및 각 요소를 검사하지 않고 동일합니다 비교할 수 싶습니다. 하나씩.

어디에서 이런 종류의 정보를 얻을 수 있습니까? 나는 가능한 한 단순한 무언가가 필요하다. 고맙습니다. 배열의 숫자 - 모든

그래서 [0,1,1,2]가 유효하지 않습니다, 별개 반복적 인 요소가 있기 때문에 1 (:

편집 : 내가 원하는 단지에 분명합니다)

년 - 숫자 물질의 위치 때문에, [0,1,2,3] [3,2,1,0]

-THE 배열 번호 0을 포함 같은 아니다 그래서 이것은 또한 고려되어야한다.

편집 : 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; 
} 

내가하지만 불행히도, 알고리즘이 작동하지 않는 리턴 라인을 무엇 아무 생각이 정직하기 : 여기 플레처의 알고리즘을 구현하기 위해 노력

좋아 . [2,1,3,0] 및 [1,3,2,0] 배열의 경우 동일한 체크섬을 얻습니다.

EDIT2 : 여기

괜찮 또 하나,이 또한 작동하지 않습니다 애들러 검사 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; 
} 

입니다. 배열 [2,0,3,1]과 [1,3,0,2]는 동일한 체크섬을 생성합니다. 나는 여기에서 희망을 잃고있다, 어떤 생각?

Answer 1

는 이제의 경우를 보자 당신의 25 개의 정수 배열. 0에서 24까지의 고유 정수의 순열을 포함 할 수 있다고 설명합니다. this page에 따르면 25가 있습니다. (25 팩토리얼) 가능 순열, 즉 15511210043330985984000000입니다. 32 비트 정수 이상은 포함될 수 있습니다.

결론은 아무리 노력해도 충돌이 발생한다는 것입니다.

지금, 여기의 위치를 ​​설명하는 간단한 알고리즘은 다음과 같습니다

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

1에서 N까지의 N 개의 고유 한 정수 배열의 경우 요소를 추가하는 것은 항상 N * (N + 1)/2가됩니다. 따라서 유일한 차이점은 주문에 있습니다. "체크섬"에 의해 충돌을 허용한다는 것을 암시하는 경우, 한 가지 방법은 연속 번호 간의 차이를 합하는 것입니다. 예를 들어, {1,2,3,4}에 대한 델타 체크섬은 1 + 1 + 1 = 3이지만 {4,3,2,1}에 대한 델타 체크섬은 -1 + -1 + -1 = -삼.

없음 요구 사항은 충돌 속도 또는 계산의 복잡성 주어되지 않았다,하지만 위의 적합하지 않는 경우, 그때는이 position dependent checksum

Answer 3

내가 당신이 원하는 것은 다음과 같은 스레드의이 질문에 대해 생각하는 것이 좋습니다

Fast permutation -> number -> permutation mapping algorithms

순열이 매핑 된 번호를 가져 와서 체크섬으로 가져옵니다. 순열 당 정확히 하나의 체크섬이 있으므로 충돌이없는 작은 체크섬을 사용할 수 없습니다.

Answer 4

귀하의 배열이 0에서 N-1까지의 숫자 순열을 포함하고 있음을 이해합니다. 유용 할 수있는 하나의 체크섬은 사전 편집 순서에 따라 배열의 순위입니다. 무엇 않습니다 그 의미 ?0, 1, 2 감안할 때 당신은 가능한 순열이

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

체크인 합이 첫 번째 숫자가 될 것이다, 그리고 당신이 배열을 만들 때 계산. 최선의 알고리즘이 차 복잡했다 보이더라도 도움이 될 수 있습니다

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

에서 제안 된 솔루션이 있습니다. 선형 복잡도를 향상 시키려면 먼저 계승 값을 캐시해야합니다.

장점은 무엇입니까? 제로 충돌.

EDIT : 계산 값 요인이 단항식 대신 전원에 사용되는 다항식의 평가 같다. 그래서 함수는

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

아이디어는 순열의 하위 범위를 얻기 위해 각각의 값을 사용하는 것입니다, 충분한 값이 독특한 순열을 정확하게 지적이다. (다항식의 하나와 같은)을 구현하기

:

1. 미리 계산 0 .... N-1! 프로그램
2. 당신이 (1)이 체크섬을 사용하여 당신이 O에 비교
3. 체크섬을 계산하면 F (요소)를 사용하여 배열을 설정할 때마다의 시작 부분에

Answer 5

어떻게 가중 합계의 체크섬은 어떻습니까? [0,1,2,3]의 예를 들어 봅시다. 처음의 그에 대한 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 

귀하의 검사는 462로 7로 씨와 제한을 선택하자, 씨앗 및 제한을 선택 [0, 1, 2, 3]. 참조 번호는 http://www.codeabbey.com/index/wiki/checksum