This is Rhys Brett-Bowen's Typepad Profile.

Join Typepad and start following Rhys Brett-Bowen's activity

Rhys Brett-Bowen

Recent Activity

I was looking up a way to select a random subset from a set (well I came up with a solution and I wanted to see if it had a name). KFY is the way to do random shuffles, but should it be used for selecting, say 3 random items from 50k by shuffling then selecting the first 3? no, it's overkill. I can see there is an algorithm earlier in the posts where you select a random number and if it's already picked then try again. Also I can see someone did this:
function shuffle(arr) {
return arr.sort(function () { return Math.sin(Math.random() * 360); });
}
in javascript. This is wrong. If anyone is using a sorting method to get a "random sort" please stop. You get biases based on the implementation of the sort method. That function is the very definition of a naive algorithm!
anyway I thought I'd put my algorithm here for people to see, it's hard to explain how it works without a white-board but does pick a random subset of a set. If you increase the subset to be the size of the original set then you end up with the whole set randomized so you can also use it for a shuffle:
//num is size of subset
//arr is an array of your set
function pickRandom(num,arr){
var ret = [];
var l = arr.length;
for(var i=0;i=0;i--){
for(var n=i-1;n>=0;n--){
if(ret[i]>=ret[n])
ret[i]++;
}
ret[i] = arr[ret[i]];
}
return ret;
}

The Danger of Naïveté

In my previous post on shuffling, I glossed over something very important. The very first thing that came to mind for a shuffle algorithm is this: for (int i = 0; i < cards.Length; i++) { int n = rand.Next(cards.Length); Swap(ref cards[i], ref cards[n]); } It's a nice, simple solution to the sh...

Rhys Brett-Bowen is now following The Typepad Team

Aug 10, 2011

Subscribe to Rhys Brett-Bowen’s Recent Activity