Genera un numero intero univoco da due numeri interi con algoritmo

Naviga le tue risposte
1

Attualmente sto cercando di trovare un algoritmo che richiederebbe almeno due numeri (ad esempio, ID utente) e quindi ottenere un numero univoco che viene generato in base a questi due numeri. Ogni numero intero può essere grande quanto un INT (11) in un database (un numero di 11 cifre)

Esempio: L'utente A (con ID: 23 , desidera interagire con l'utente B (ID: 20 ) e un numero univoco di quelli devono essere generati due numeri, ad esempio 4094 . Questo numero potrebbe o potrebbe non essere reversibile fino al 23 e 20 (non mi interessa davvero) ma è importante solo che questi due numeri producano sempre lo stesso numero. È molto importante, indipendentemente dall'ordine (23-20 o 20-23) che il numero generato sia sempre lo stesso).

  • Stavo pensando che sarebbe stato più semplice usare una qualche funzione di hashing (SHA2, poiché MD5 consente le collisioni).
  • Ho anche controllato la formula suggerita di:

π(a,b)=12(a+b)(a+b+1)+b

ma non funziona quando si scambiano A e B.

  • So che questo può essere fatto da una tabella di database, che memorizza il file relazione tra i due tavoli ma voglio evitarlo facendolo nel runtime.

Hai qualche buona idea per una formula matematica singola che potrebbe fare il trucco per me?

    
posta Placeholder 21.10.2014 - 14:14
fonte

3 risposte

0

Ho modificato la formula di Cantor originale per coppie:

pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2

A questo personalizzato:

pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + (k1*k2)

Finora tutti i numeri univoci, non importa f (A, B) o f (A, B) . Se qualcuno può migliorare l'algoritmo, sei il benvenuto, non sono così bravo nei calcoli matematici e nella progressione.

Ecco un esempio di risultato:

    
risposta data 21.10.2014 - 16:15
fonte
5

È facile creare uno schema, ma è necessario un intervallo di numeri che sia almeno pari al quadrato del possibile intervallo di numeri per gli ID. Altrimenti, non può garantire ciò di cui hai bisogno, ad esempio che il valore combinato è univoco (google "principio pigeonhole"). Ciò probabilmente significa che è necessario un tipo di dati più grande per memorizzare il numero combinato rispetto all'ID.

La soluzione reale è semplice: basta formattare entrambi i numeri fino a una larghezza fissa e concatenarli. Ad esempio, 35 e 534 darebbero 000534000035, che equivale a 534000035. È allettante tentare di costruire uno schema più "efficiente", ma dal momento che non può funzionare, secondo il principio del pigeonhole, si potrebbe anche fare la cosa più primitiva che si possa immaginare.

Modifica: ho mancato il requisito che la mappatura deve essere simmetrica. Per questo, devi prima ordinare i due numeri in modo coerente.

(Si noti che, a meno che non si utilizzi assolutamente, in modo positivo, un handle combinato numerico , è quasi certamente molto più facile generare una combinazione di string ).

    
risposta data 21.10.2014 - 14:18
fonte
4

Se solo il problema è che vuoi che i due numeri siano intercambiabili, basta ordinarli. Fai in modo che il numero più grande sia sempre il primo e il secondo più piccolo. Quindi puoi utilizzare la Funzione di accoppiamento che hai già provato.

    
risposta data 21.10.2014 - 14:25
fonte

Leggi altre domande sui tag

Come affrontare la progettazione del programma rispetto alle strutture e agli algoritmi di dati: esiste un elemento di riferimento del processo di progettazione OO per d.s.'s + algs? [chiuso] In quale linguaggio di programmazione è nato il blocco finale?