Tinyurl in stile codice univoco: Potenziale algoritmo per evitare collisioni

Question

Ho un sistema che richiede un codice univoco a 6 cifre per rappresentare un oggetto, e sto cercando di pensare a un buon algoritmo per la generazione di loro. Qui ci sono le pre-reqs:

• sto usando un sistema a base 20 (senza tappi, numeri, vocali, o l per evitare confusione e cattivi parole)
  • La base-20 consente di 64 milioni di combinazioni
• I adoperaste potenzialmente 5-10.000 voci in una sola volta, quindi in teoria userei inserimenti di massa, il che significa che utilizzando una chiave unica, probabilmente non sarà efficace o abbastanza (soprattutto se v'è stato acquistato un sacco di collisioni )
• Non è fuori questione per riempire il 10% delle combinazioni quindi non c'è un alto potenziale per un sacco di collisioni
• Voglio assicurarsi che i codici sono non-consecutivi

ho avuto un'idea che suonava come avrebbe funzionato, ma non sono abbastanza bravo in matematica per capire come implementarlo: se comincio a 0 e l'incremento da N, poi convertire in Base-20, sembra come ci dovrebbe essere un valore per N che mi permette di contare ogni valore da 0-63,999,999 prima di ripetere qualsiasi.

Ad esempio, passando da 0 a 9 con N = 3 (quindi 10 mod 3):. 0, 3, 6, 9, 2, 5, 8, 1, 4, 7

C'è qualche metodo di matematica magica per capire i valori di N per un certo numero di più grande che è in grado di contare attraverso l'intera gamma senza ripetere? Idealmente, il numero scelgo sarebbe sorta di salto intorno al set in modo tale che non era ovvio che ci fosse un disegno, ma non sono sicuro di come possibile che sia.

In alternativa, un algoritmo di hashing che garantiva l'unicità dei valori 0-64.000.000 avrebbe funzionato, ma io sono troppo stupido per sapere se è possibile.

Answer 1

Tutto ciò che serve è un numero che condivide nessun fattore chiave con il vostro spazio. il valore più semplice è quello di utilizzare un numero primo. È possibile google per i grandi numeri primi, o utilizzare http://primes.utm.edu/lists/ piccola / 10000.txt

Answer 2

Qualsiasi numero primo che non è un fattore della lunghezza della sequenza dovrebbe essere in grado di coprire la sequenza senza ripetere. Per 64000000, questo significa che non si dovrebbe usare 2 o 5. Naturalmente, se non si desidera loro di essere generati consecutivamente, li genera 2 o 5 a parte è probabilmente anche non molto buona. Personalmente, come il numero 73973!

Answer 3

C'è un altro metodo per ottenere un risultato simile (saltando l'intero set dei valori senza ripetere, nonconsequtively), senza utilizzare i numeri primi - utilizzando massimo sequenze di lunghezza , che è possibile generare utilizzando registri a scorrimento appositamente costruiti.

Answer 4

La mia matematica è un po 'arrugginito, ma penso che è sufficiente per garantire che il GCF di N e 64 milioni è 1. Mi piacerebbe andare con un numero primo (che non divide equamente in 64 milioni) solo in caso però.

Answer 5

@ Nick Lewis:

Bene, solo se il numero primo non divide 64 milioni. Così, per gli scopi del interrogante, numeri come 2 o 5 probabilmente non sarebbe consigliabile.

Answer 6

Non reinventare la ruota: http://en.wikipedia.org/wiki/Universally_Unique_Identifier