What would be the best way to shuffle an array of numbers with the condition that each number must be +3 or -3 of the next/prev number? So, for example [0,1] wouldn't work, but [0,3] would.
Thanks!
2
-
2It's not always possible -- you give one example where it isn't. In general you won't always be able to do it. What's the underlying problem you're trying to solve?tvanfosson– tvanfosson2011-02-23 02:14:42 +00:00Commented Feb 23, 2011 at 2:14
-
Yeah, I know that it's not always possible.. basically I'm trying to build an "image grid" that highlights random images --it loops -- the highlighted images have a label that covers other images if they are too close together -- check out this screenshot (it might be better than trying to explain it) cl.ly/261Y2F0200442e220y3zRyanLynch– RyanLynch2011-02-23 02:30:25 +00:00Commented Feb 23, 2011 at 2:30
Add a comment
|
4 Answers
Looking at the screenshot it seems you're wanting to pick a random assortment from the list, with no 2 choices being within 3 of each other. This code takes an array, and gives you a subset of the array satisfying that condition. You can specify a maximum number of selections too, although you might not always get that many.
var src = [0,1,2,3,4,5,6,7,8,9,10,11,12];
var getRnd = function(max){
var output = [];
var newSrc = src.slice();
var test, index, i, safe;
while (newSrc.length > 0 && output.length < max){
index = Math.floor(Math.random()*newSrc.length);
test = newSrc.splice(index,1);
//Make sure it's not within 3
safe = true;
for (i=0; i<output.length;i++){
if(Math.abs(test-output[i]) < 3){
//abort!
safe=false;
}
}
if(safe){
output.push(test);
}
}
return output;
};
alert(getRnd(4));
1 Comment
RyanLynch
Exactly what I was trying to do. Thank you!
A way (likley not the fastes) would be to:
- sort array
- pick random element to start new shuffled array with (mark element in sorted array as used or remove)
- with binary search find next element that is +3 or -3 for the last one (randomly pick between -3 and +3). Make sure element is not marked as used before (otherwise find another one)
- repeat 3 till you can find elements.
- you either picked all elements from sorted array or such shuffling is not possible.
I think you get O(N*logN) with this (sorting N*logN and picking N elements with logN for each serch).
Comments
Assuming that the values in the array cannot be duplicated.
function one(array, mod){
var modArray = [];
for(var index in array){
var item = array[index];
var itemMod = item%3;
if(itemMod === mod){
modArray.push(item);
}
}
return modArray();
}
function two(modArray){
var sortedArray = // sort highest to lowest
for(var index in sortedArray ){
var item = array[index];
if(index > 0 && item[index-1] === item[index]-3){
}else{return false;}
}
return sortedArray.length;
}
function main(array){
var a1 = one(array, 0);
var a2 = one(array, 1);
var a3 = one(array, 2);
var a1c = two(a1);
var a2c = two(a2);
var a3c = two(a3);
return // if a1c is greatest then a1, if a2c greatest then a2 ... etc
}
Comments
I think you must be using the phrase "shuffle" in some non-standard way. If all of the numbers are already within +-3 of each other, then sorting the array will put them in the right order, unless there are duplicates, I guess.
More examples would probably be helpful. For instance, are these examples valid, and the sort of thing you're looking for?
[0, 3, 3] -> [3, 0, 3]
[9, 3, 6, 0, 6] -> [0, 3, 6, 9, 6]
[3, 3, 6, 0, 6] -> [0, 3, 6, 3, 6]
It feels like this is probably a solved problem in graph theory - some kind of network traversal with a maximum/minimum cost function.
