Questo algoritmo produce permute uniformemente casuali?

Question

Sto studiando CLRS e ho riscontrato un problema nell'algoritmo di shuffling. Questo produce una permutazione uniforme casuale?

1 PERMUTE-WITH-ALL-IDENTITY(A) 
2 n = A.length 
3 for i = 1 to n 
4  swap A[i] with A[RANDOM(1,n)] 
5  swap A[i] with A[RANDOM(i+1,n)] 

La mia richiesta: No. non è così. Perché, non ci saranno possibili permutazioni dovute alla linea 4. E, non è divisibile per n! che è il numero di permutazioni distinte.

Potete, per favore, confermare se il mio ragionamento è corretto?

Answer 1

Per i principianti, penso che ci sia un bug nello pseudocodice. Nella riga 4, credo che ci sia un errore di limite quando i = n, poiché ciò richiederebbe un numero casuale tra n + 1 e n. In seguito, ho corretto questo assumendo il codice è il seguente:

1 PERMUTE-WITH-ALL-IDENTITY(A) 
2 n = A.length 
3 for i = 1 to n 
4  swap A[i] with A[RANDOM(1,n)] 
5  swap A[i] with A[RANDOM(i,n)] 

Se questo è il codice, quindi credo che la risposta è no, questo non produce permutazioni uniformemente-casuali. Non ho una prova matematica che sia questo il caso, ma ho un pezzo di codice C++ che bruta-forza tutti i possibili percorsi attraverso PERMUTE-WITH-ALL-IDENTITY e conta il numero di volte in cui ciascuna permutazione viene prodotta. Ho eseguito quel codice e testato l'algoritmo sulle permutazioni su sequenze di lunghezza da 0 a 4, compresa, e ho scoperto che non tutte le permutazioni sono ugualmente probabili.

Ecco il codice:

#include <iostream> 
#include <map> 
#include <vector> 
#include <algorithm> 
using namespace std; 

/* Maximum size of a sequence to permute. */ 
const size_t kMaxSize = 4; 

/** 
* Given a frequencies map associating permutations to the number of times 
* that we've seen them, displays a visual report of the permutations 
* and their frequencies. 
* 
* @param frequencies The frequencies map. 
*/ 
void reportResults(const map<vector<int>, size_t>& frequencies, size_t size) { 
    cout << "Report for size " << size << endl; 
    cout << "===================================================" << endl; 

    /* Print out the map. */ 
    cout << " Map entries:" << endl; 
    for (const auto& entry: frequencies) { 
    cout << " "; 
    for (const auto& num: entry.first) { 
     cout << num; 
    } 
    cout << ": " << entry.second << endl; 
    } 

    cout << "===================================================" << endl; 
    cout << endl << endl; 
} 

/** 
* Traces through all possible executions of the algorithm, recording 
* the number of times that each outcome occurs. This algorithm uses 
* exhaustive recursion to explore the full space, assuming that the 
* underlying random generator is uniform. 
* 
* @param elems The elements in the sequence. It's assumed that initially 
* these are in sorted order, but as the algorithm progresses it will 
* become progressively more permuted. 
* @param frequencies A map from permutations to the number of times that 
* they appear. 
* @param index The index through the main loop that we are currently in. 
* This is the variable 'i' in the pseudocode. 
* @param size The length of the vector. This isn't strictly necessary, 
* but it makes the code a bit cleaner. 
*/ 
void recPopulate(const vector<int>& elems, 
       map<vector<int>, size_t>& frequencies, 
       size_t index, size_t size) { 
    /* If we've finished permuting everything, record in the frequency map 
    * that we've seen this permutation one more time. 
    */ 
    if (index == size) { 
    frequencies[elems]++; 
    } else { 
    /* For all possible pairs of a first swap and a second swap, try that 
    * out and see what happens. 
    */ 
    for (size_t i = 0; i < size; i++) {  // First swap index 
     for (size_t j = index; j < size; j++) { // Second swap index 
     /* Make a clean copy of the vector to permute. */ 
     vector<int> newElems = elems; 

     /* Perform the swaps. */ 
     swap(newElems[i], newElems[index]); 
     swap(newElems[j], newElems[index]); 

     /* Recursively explore all possible executions of the algorithm 
     * from this point forward. 
     */ 
     recPopulate(newElems, frequencies, index + 1, size); 
     } 
    } 
    } 
} 

/** 
* Traces through all possible executions of the proposed algorithm, 
* building a frequency map associating each permutation with the 
* number of possible executions that arrive there. 
* 
* @param size The number of elements in the initial sequence. 
* @return A frequency map from permutations to the number of times that 
* permutation can be generated. 
*/ 
map<vector<int>, size_t> populateFrequencies(size_t size) { 
    /* Create the sequence 0, 1, 2, ..., size - 1 */ 
    vector<int> elems(size); 
    iota(elems.begin(), elems.end(), 0); 

    map<vector<int>, size_t> frequencies; 
    recPopulate(elems, frequencies, 0, elems.size()); 
    return frequencies; 
} 

int main() { 
    for (size_t size = 0; size <= kMaxSize; size++) { 
    map<vector<int>, size_t> frequencies = populateFrequencies(size); 
    reportResults(frequencies, size); 
    } 
} 

Questo programma genera report che mostrano, per ogni permutazione, il numero di possibili percorsi di esecuzione attraverso l'algoritmo che producono quel permutazione. L'output per permutazioni di quattro elementi è mostrato di seguito. Dato che ogni percorso di esecuzione la stessa probabilità, dato che i numeri qui non sono gli stessi, si può concludere che l'algoritmo è non uniformemente casuale:

Report for size 4 
=================================================== 
    Map entries: 
    0123: 214 
    0132: 268 
    0213: 267 
    0231: 316 
    0312: 242 
    0321: 229 
    1023: 268 
    1032: 322 
    1203: 312 
    1230: 349 
    1302: 287 
    1320: 262 
    2013: 242 
    2031: 283 
    2103: 233 
    2130: 262 
    2301: 252 
    2310: 240 
    3012: 213 
    3021: 208 
    3102: 204 
    3120: 187 
    3201: 248 
: 236 
=================================================== 

L'analisi sopra cerniere sul fatto che

1. Il mio codice è corretto, e
2. La mia interpretazione dello pseudocodice è corretta.

Se uno di questi è sbagliato, sarei felice di ritirare o modificare questa risposta. Per favore fatemi sapere se ho commesso un errore qui!

Spero che questo aiuti!

Answer 2

L'analisi di cui sopra suggerisce un chi di 147 con 23 gradi di libertà, il che significa che il valore P è < 0,00001. Questo indica un adattamento molto scadente con una presunta distribuzione uniforme.

Ma.

Sembra esserci solo 6144 campioni totali. Se guardi la casualità, avrei pensato che sarebbero state necessarie più prove. Potrebbe essere che il P-Value si sposti verso una posizione più favorevole dopo 1000 run. Tuttavia, non rieseguire il reseeding del generatore casuale tra una corsa e l'altra.