È possibile comprimere la permutazione casuale vera usando l'interpolazione polinomiale di basso ordine? Se sì, come può essere raggiunto?
È possibile comprimere la permutazione casuale vera usando l'interpolazione polinomiale di basso ordine? Se sì, come può essere raggiunto?
Questo è solo un commento esteso, troppo lungo per un commento. In primo luogo, l'abstract nel link link tratta della "compressione dei dati", ma non "casuale" di per sé. E come @CandiedOrange ha menzionato per la prima volta, i dati casuali non sono comprimibili. E questo è semplicemente per definizione, ad es. Google "complessità Kolmogorov". Se puoi comprimere una stringa, non è casuale - per definizione.
Tuttavia, come accennato nel mio commento, le permutazioni non sono del tutto casuali poiché sono vincolate dal requisito che ogni intero 1,2, ..., N appare esattamente una volta. E ciò significa N! possibili permutazioni, contro N ^ N > N! possibili sequenze casuali.
Quindi ecco una possibile strategia di compressione delle permutazioni, sebbene non abbia assolutamente nulla a che fare con l'interpolazione. Scegli un'enumerazione delle permutazioni di 1 ... N , per cui puoi ricostruire una permutazione per il suo indice 1 ... N! nell'enumerazione. E quell'indice richiede solo log_2 (N!) bit. In confronto, un'enumerazione di tutte le sequenze richiederebbe i bit log_2 (N ^ N) per specificare un indice, in cui le permutazioni casuali sono comprimibili rispetto alle sequenze casuali.
Leggi altre domande sui tag compression