[Algorytmy] Hash dla permutacji

[Borneq]

Chcę każdą permutację oznaczyć 32 lub lepiej 64 bitowych hashem
ma mieć własności:
- operuję na liczbach rzędu 1000, nie bajtach
- możliwość generowania przyrostowego gdy mam swap dwóch elementów, podobnie jak ma to funkcja XOR

Dodano po 1 godzinie 27 minutach 15 sekundach:
A może zmodyfikowany XOR? XOR jest nieczuły na kolejność elementów, ale może xor wraz z numerem pozycji ? czyli 0 xor vector[0[ xor 1 xor vector[1] xor 2 xor vector[2]...?
jest inkrementalny.
Wada: dla małych liczb również xor będzie małą liczbą, nie 32 czy 64 bitową. Czy nie będzie konflików w takim razie gdy dwie permutacje będą miały ten sam hash?

[Dasio11]

czyli 0 xor vector[0[ xor 1 xor vector[1] xor 2 xor vector[2]...?

Jeśli vector ma być permutacją, to powyższe wyrażenie zawsze da wartość zerową.

[Borneq]

rozumiem że xor wszystkich kolejnych liczb może dać wartość zerową, ale gdy pomiedzy liczbami są ich pozycje? Teraz rozumiem xor jest nieczuły na kolejność mamy diwe permutację, xor jednej i drugiej zero więc razem zero.
Czy można coś dodać, jakąś rotację, shift, ale by zachować inkrementalność?

Dodano po 32 minutach 17 sekundach:
Suma Fletchera?

Dodano po 3 godzinach 16 minutach 41 sekundach:
Już wiem: \(\displaystyle{ \sum_{i=0}^{n-1}tab_{i}\cdot (i+1) }\)

kod testujący:

Kod: Zaznacz cały

#include <iostream>
#include <vector>

using namespace std;

int sum1 (vector<int8_t> &v) {
    int res = 1;
    for (int i=0; i<v.size();i++){
        res += v[i]*(i+1);
    }
    return res;
}


int main() {
    vector<int8_t> v;
    v.clear();
    v.push_back(1);
    v.push_back(3);
    v.push_back(32);
    v.push_back(2);
    int sum = sum1(v);
    std::cout << sum << std::endl;
    v[2]=127;
    int fastsum = sum + 3*(127-32);
    std::cout << fastsum << " " << sum1(v) << std::endl;
    return 0;
}