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
- Il mio codice è corretto, e
- 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!
Ma state scegliendo le possibilità 'n!' A causa della linea 5. – Teepeemm
@Teepeemm Quindi, la linea 4 viene semplicemente ignorata. Tranne, si assicura che possiamo ottenere elementi nello stesso posto, cosa che non sarebbe possibile senza la linea 4. Ho ragione? –
Suggerisco di superarlo quando 'n == 3': vedi se riesci a capire le probabilità di ciascuno dei sei possibili risultati. (Suggerimento: non sono uguali.) –