math - Does this algorithm produce uniformly-random permuations? -

i studying clrs , found problem on shuffling algorithm. produce uniformly random permutations?

1 permute-with-all-identity(a) 2    n = a.length 3    = 1 n 4        swap a[i] a[random(1,n)] 5        swap a[i] a[random(i+1,n)]  

my claim: no. not. because, there n^n possible permutations due line 4. and, not divisible n! number of distinct permutations.

can you, please, confirm if reasoning correct?

for starters, think there's bug in pseudocode. in line 4, believe there's bounds error when = n, since ask random number between n+1 , n. in follows, i've corrected assuming code following:

1 permute-with-all-identity(a) 2    n = a.length 3    = 1 n 4        swap a[i] a[random(1,n)] 5        swap a[i] a[random(i,n)]  

if code, believe answer no, not produce uniformly-random permutations. don't have mathematical proof case, have piece of c++ code brute-forces possible paths through permute-with-all-identity , counts number of times each permutation produced. ran code , tested algorithm on permutations on sequences of length 0 through 4, inclusive, , found not permutations equally likely.

here's code:

#include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std;  /* maximum size of sequence permute. */ const size_t kmaxsize = 4;  /**  * given frequencies map associating permutations number of times  * we've seen them, displays visual report of permutations  * , frequencies.  *  * @param frequencies frequencies map.  */ void reportresults(const map<vector<int>, size_t>& frequencies, size_t size) {   cout << "report size " << size << endl;   cout << "===================================================" << endl;      /* print out map. */   cout << "  map entries:" << endl;   (const auto& entry: frequencies) {     cout << "    ";     (const auto& num: entry.first) {       cout << num;     }     cout << ": " << entry.second << endl;   }    cout << "===================================================" << endl;   cout << endl << endl; }  /**  * traces through possible executions of algorithm, recording  * number of times each outcome occurs. algorithm uses  * exhaustive recursion explore full space, assuming  * underlying random generator uniform.  *  * @param elems elements in sequence. it's assumed  *    these in sorted order, algorithm progresses  *    become progressively more permuted.  * @param frequencies map permutations number of times  *    appear.  * @param index index through main loop in.  *    variable 'i' in pseudocode.  * @param size length of vector. isn't strictly necessary,  *    makes code 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 frequency map    * we've seen permutation 1 more time.    */   if (index == size) {     frequencies[elems]++;   } else {     /* possible pairs of first swap , second swap, try      * out , see happens.      */     (size_t = 0; < size; i++) {        // first swap index       (size_t j = index; j < size; j++) {  // second swap index         /* make clean copy of vector permute. */         vector<int> newelems = elems;          /* perform swaps. */         swap(newelems[i], newelems[index]);         swap(newelems[j], newelems[index]);          /* recursively explore possible executions of algorithm          * point forward.          */         recpopulate(newelems, frequencies, index + 1, size);       }     }   } }  /**  * traces through possible executions of proposed algorithm,  * building frequency map associating each permutation  * number of possible executions arrive there.  *  * @param size number of elements in initial sequence.  * @return frequency map permutations number of times  *    permutation can generated.  */ map<vector<int>, size_t> populatefrequencies(size_t size) {   /* create 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() {   (size_t size = 0; size <= kmaxsize; size++) {     map<vector<int>, size_t> frequencies = populatefrequencies(size);     reportresults(frequencies, size);   } } 

this program generates reports show, each permutation, number of possible execution paths through algorithm produce permutation. output permutations of 4 elements shown below. given each execution path equally likely, since numbers here aren't same, can conclude algorithm not uniformly random:

report 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     3210: 236 =================================================== 

the above analysis hinges on fact that

1. my code correct, and
2. my interpretation of pseudocode correct.

if either of these wrong, i'd happy retract or edit answer. please let me know if i've made mistake here!

hope helps!