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

  • 1

    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 {
        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;
        std::vector<int> val;

  • 0

    @prashrockgmail.com Good explanation, and implementation too!

Log in to reply

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