CODEWITHSUNDEEP
javascript
checkingJS
checkingJS

Reputation: 47

Shuffle an Array coding challenge. trouble understanding one part

Question: Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

Answer:

 var Solution = function(nums) {

// hold nums in Solution

   this.nums = nums;
};

Solution.prototype.reset = function() {
   return this.nums;
};

Solution.prototype.shuffle = function() {

// create a copy of this.nums, shuffle it, and return it0

const shuffled = this.nums.slice();
const n = shuffled.length;
const swap = (arr, i, j) => {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// swap elements with random elements
for (let i = 0; i < n; i++) 
    swap(shuffled, i, Math.floor(Math.random() * n));

return shuffled;
};

My question: The Math.floor(Math.random() * n ) you are getting a random index out of the length of the array. I do not understand, can't this code make duplicates? Say if the length is 3. Cant the formula get the index of 2 and another index of 2, thus making duplicate indexes. Can anyone clarify something I am misunderstanding. Thanks. Does Math.random automatically withdraw indexes that have been used?

Upvotes: 1

Views: 120

Answers (2)

Code Maniac
Code Maniac

Reputation: 37755

Math.floor(Math.random() * n) Yes it can eve-valuate to same index but here you're using the number to swap element so this is ok.

Does Math.random automatically withdraw indexes that have been used?

No it doesn't you need to keep track of previously generated values

What you can do it is have a variable a object or Map to keep track of previously add index if the random generated index is not already included in that variable than add it to final output else again generate a new index,

But in this case it is not needed.

Upvotes: 1

CertainPerformance
CertainPerformance

Reputation: 370699

Yes, the Math.floor(Math.random() * n) expression can evaluate to the same number multiple times, but that's OK, because the random number is being used in swap, which switches the number at index i with the number at the chosen random index.

If the random index was taken from the original array and added to the array to be returned, eg

const randIndex = Math.floor(Math.random() * n);
arrToBeReturned.push(arr[randIndex]);

you'd be right, but that's not what the algorithm is doing. Imagine randomly sorting an array of [1, 2, 3]:

First iteration of loop: i is 0, random index chosen is 2. Swap indicies 0 and 2:

[3, 2, 1]

Second iteration: i is 1, random index chosen is 2. Swap indicies 1 and 2:

[3, 1, 2]

Third iteration: i is 2, random index chosen is 2. Swap indicies 2 and 2:

[3, 1, 2]

With this code, every index is randomly swapped with another index at least one time, ensuring that by the end, the array is randomized without bias (assuming Math.random is trustworthy).

Upvotes: 1

Related Questions