# C++ Knuth Shuffle (Fisher-Yates Shuffle) Implementation (352 ms)

• The number of permutations for a given vector of size 'n' without replacement is nPn ( = n!). The easiest way to solve this problem is to use a Knuth Shuffle algorithm as explained in Robert Sedgewick's lecture.

Note: Need to pick a new random number (@idx) in each loop iteration such that it lies in the range [0, (i + 1)]. If 'n' is used instead of (i + 1) as the upper bound, then this would cause a n^n possible permutations which is not correct. Below is my submission:

``````class Solution {
public:
Solution(std::vector<int> nums) : val(nums) {
srand( time(NULL) ^ 100003); //current time XOR prime
}

/** Resets the array to its original configuration and return it. */
std::vector<int> reset() { return val; }

/** Returns a random shuffling of the array. */
std::vector<int> shuffle() {
std::vector<int> cpy(val);
/* Knuth Shuffle main loop                                */
for(size_t i = 1; i < cpy.size(); ++i) {
const auto j = rand() % (i + 1);    /* 0 <= j <= i    */
std::swap(cpy[i], cpy[j]);
}
return cpy;
}
private:
std::vector<int> val;
};
``````

• @prashrockgmail.com Good explanation, and implementation too!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.