Non è improbabile che ciò che voglio fare non sia possibile, ma non fa male a chiedere.
Immaginate un insieme di liste, ciascuna contenente interi positivi (nel mio caso, una lista consiste sempre di quattro numeri interi, ma ciò non dovrebbe fare alcuna differenza).
a = [35, 2, 123684, 647]
b = [453, 346457546457, 6, 0]
c = ...
Poi c'è un alfabeto, per esempio
alphabet = [A, .., Z, a, .., z, 0, .., 9]
Quello che voglio fare è creare una funzione che trasformi gli elenchi in stringhe usando l'alfabeto.
f: (list[Int], alphabet) -> string
I requisiti per f sono i seguenti:
-
f dovrebbe essere iniettivo, nel senso che due liste diverse portano sempre a due stringhe diverse e una lista specifica produce sempre la stessa stringa ogni volta che viene chiamato f.
Note:
- Due liste sono uguali se entrambe contengono gli stessi elementi nello stesso ordine.
- Va bene se le trasformazioni di liste diverse che usano alfabeti diversi danno come risultato la stessa stringa. Il requisito univoco si applica solo alla trasformazione di elenchi diversi utilizzando lo stesso alfabeto.
- Non è richiesta una funzione inversa.
- Ora la parte difficile: le stringhe risultanti devono essere il più corte possibile.
Tutti i numeri sono interi a 32 bit. Ma il fatto che siano di dimensioni molto diverse (l'intervallo possibile va da 0 a Int.max ) dovrebbe essere preso in considerazione. Concatenare insieme le rappresentazioni a 32 bit (o fare qualcos'altro che usa pezzi di dimensioni fisse) non è una soluzione praticabile.
Un approccio potrebbe essere quello di scegliere un carattere dell'alfabeto e usarlo come separatore. Questo è fondamentalmente ciò che fanno gli hashids . Per esempio. se 'A' è il separatore, tutte le stringhe risultanti avranno questo aspetto: "...A...A...A..." .
Cosa non mi piace di questa soluzione:
- La dimensione effettiva dell'alfabeto è ridotta di uno, poiché uno dei caratteri può essere usato solo come separatore, non per i numeri di codifica. Ciò si traduce in stringhe più lunghe, soprattutto quando si usano alfabeti piccoli
- Anche il separatore estende la stringa. La codifica di un elenco di quattro numeri interi significa tre caratteri aggiuntivi nel risultato.
Mi chiedo se c'è una soluzione meno ovvia al problema, forse un approccio più matematico? In sostanza, il problema è "unire" più numeri in un unico numero (unico).