Unikalny kod w stylu Tinyurl: potencjalny algorytm zapobiegający kolizjom

Question

Mam system, który wymaga unikalnego 6-cyfrowego kodu do przedstawienia obiektu i staram się wymyślić dobry algorytm do ich generowania. Oto wstępnie reqs:

• ja przy użyciu układu bazowego 20 (bez nasadki, liczb, samogłoski i l dla większej przejrzystości i zły słów)
  • baza-20 umożliwia 64 miliony kombinacji
• Będę wstawiać potencjalnie 5-10 tysięcy wpisów na raz, więc teoretycznie użyłbym wkładek luzem, co oznacza, że ​​użycie unikalnego klucza prawdopodobnie nie będzie wydajne lub ładne (szczególnie jeśli zaczyna być mnóstwem kolizji)
• To nie jest z qu estion aby wypełnić 10% kombinacji więc istnieje duży potencjał dla wielu kolizji
• Chcę upewnić się, że kody są dla kolejnych

miałem pojęcia, co zabrzmiało jak to działa, ale Nie jestem wystarczająco dobry z matematyki, aby dowiedzieć się, jak ją zaimplementować: jeśli zaczynam od 0 i zwiększam o N, to konwertuję na base-20, wydaje się, że powinna być pewna wartość dla N, która pozwala mi liczyć każdą wartość z 0-6999999 przed powtórzeniem którejkolwiek.

Na przykład, począwszy od 0 do 9, stosując n = 3 (a więc 10 mod 3): 0, 3, 6, 9, 2, 5, 8, 1, 4, 7

jest jakiś magiczna metoda matematyczna do wyznaczania wartości N dla pewnej większej liczby, która jest w stanie zliczyć cały zakres bez powtarzania? W idealnej sytuacji wybrana przeze mnie liczba przeskakuje w taki sposób, że nie było oczywiste, że istnieje wzór, ale nie jestem pewien, jak to możliwe.

Alternatywnie, algorytm mieszający, który zagwarantowałby wyjątkowość dla wartości 0-64 miliona, działałby, ale jestem zbyt głupi, aby wiedzieć, czy to możliwe.

Answer 1

Wszystko, czego potrzebujesz, to numer, który nie ma żadnych czynników w twoim kluczowym miejscu. Najłatwiej jest użyć liczby pierwszej. Możesz google dla dużych liczb pierwszych lub użyć http://primes.utm.edu/lists/small/10000.txt

Answer 2

Moja matematyka jest trochę zardzewiała, ale myślę, że musisz tylko upewnić się, że GCF N i 64 miliona to 1. Wybrałbym liczbę pierwszą (to nie dzieli się równomiernie na 64 miliony) na wszelki wypadek.

Answer 3

Dowolna liczba pierwsza, która nie jest czynnikiem długości sekwencji, powinna być w stanie rozciągnąć sekwencję bez powtarzania. Dla 64000000 oznacza to, że nie powinieneś używać 2 lub 5. Oczywiście, jeśli nie chcesz, aby były generowane kolejno, generowanie ich 2 lub 5 osobno prawdopodobnie również nie jest zbyt dobre. Osobiście podoba mi się numer 73973!

Answer 4

Nie wyważać otwartych drzwi: http://en.wikipedia.org/wiki/Universally_Unique_Identifier

Answer 5

@Nick Lewis:

Cóż, tylko wtedy, gdy liczba pierwsza nie dzieli 64 mln. Tak więc, dla celów pytającego, liczby takie jak 2 lub 5 prawdopodobnie nie byłyby wskazane.

Answer 6

Istnieje inna metoda uzyskania podobnego wyniku (przeskakiwanie przez cały zestaw wartości bez powtarzania, niekonkluzywnie), bez użycia liczb pierwszych - za pomocą maximum length sequences, które można wygenerować za pomocą specjalnie skonstruowanych rejestrów przesuwnych.