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


  • 1
    P

    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;
    };
    

  • 0
    L

    @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.