Saturday, July 21, 2007

Shuffled Arrays

{

One of my weaknesses is that I love puzzles. And once I'm puzzle solving, I usually dwell on the problem beyond its worth. I recently saw a job ad - I'll leave this post disconnected - that had a quiz associated with it. The quiz amounts, basically, to shuffling items in an array (javascript).

My first stab was intuitive, but I wonder if it's the most optimal because it relies on a lot of discarded data. In my loop generating a random order, I essentially go through an undetermined amount of times discarding results that already exist in the randomized array. Additionally the array with random numbers is just for positioning and is probably unnecessary.
Here is the code:


function BuildArray(){
// just builds a random array to work with
var testArray = new Array();
testArray.push('Test 0');
testArray.push('Test 1');
testArray.push('Test 2');
testArray.push('Test 3');
return testArray;
}

function GetShiftOrder(testObject){
// this is what sorts things out
var upperBound = testObject.length;
var newOrder = new Array();
var shuffledArray = new Array();
builder:
while(newOrder.length < upperBound){
n = parseInt(Math.random() * upperBound);
for(i=0;i<newOrder.length;i++){
if(newOrder[i] == n){
continue builder;
}
}
newOrder.push(n);
shuffledArray.push(testObject[n]);
}
alert(newOrder + '\n' + shuffledArray);
}


I was thinking about this today and it may be more effecient to make a random number of passes at the array swapping pairs of items. A shuffling cards approach may be slightly more effecient although to have meaningful swaps there would need to be a minimum number of passes - and additional complexity with making sure pairs were swapped in random pattern.

Anyway, it was interesting and I'm always curious about more elegant solutions.

}

No comments: