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?
[Algorytmy] Hash dla permutacji
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Hash dla permutacji
Jeśli
vector
ma być permutacją, to powyższe wyrażenie zawsze da wartość zerową.- Borneq
- Użytkownik
- Posty: 247
- Rejestracja: 23 lip 2010, o 07:50
- Płeć: Mężczyzna
- Lokalizacja: geo:lat=0 geo:lon=0
- Podziękował: 13 razy
Re: Hash dla permutacji
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:
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;
}