Shuffle an Array
This problem is a mix of simple design, coding and math. Question asks to design a class to shuffle and array, take a look: https://leetcode.com/problems/shuffle-an-array/description/
What I decided to do was:
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();
What I decided to do was:
- Keep a private member which is the original array. Use the clone function in C# to copy the array from/to
- Create a private random object too
- The reset returns the original array
- The shuffling first makes a copy of the original again
- OK, now for the actual shuffling: for each index i, pick a random index between [i, array length) (notice the inclusive and exclusive syntax!) and swap the elements
That's it! Cheers, and below you can find me with my dream toy, in my dreams!
public class Solution
{
private int[] original;
Random rd = null;
public Solution(int[] nums)
{
original = (int[])nums.Clone();
rd = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] Reset()
{
return original;
}
/** Returns a random shuffling of the array. */
public int[] Shuffle()
{
int[] nums = (int[])original.Clone();
for (int i = 0; i < nums.Length; i++)
{
int j = rd.Next(0, nums.Length - i) + i;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
}
Comments
I guess great minds do think alike :D You have came up with one of the best and simplest ways of shuffling an array - Fisher-Yates shuffle :)
Reply DeleteC++ implementation is below:
/** Returns a random shuffling of the array. */
vector shuffle() {
vector shuffled = nums;
for (int i = 0; i < nums.size(); ++i) {
swap(shuffled[i], shuffled[i + rand() % (nums.size() - i)]);
}
return shuffled;
}
Cheers,
Taras
Should they then call it Fisher-Yates-Barros method? :) cheers my dear!!!
Reply Deletehaha, now that you're mentioning this, I've realized that it makes a lot of sense to rename it :D
DeletePost a Comment
[γγ¬γΌγ ]