Javascript array shuffle with padding

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.

开发者_如何学Go

Thanks!

---

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));

---

A way (likley not the fastes) would be to:

1. sort array
2. pick random element to start new shuffled array with (mark element in sorted array as used or remove)
3. 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)
4. repeat 3 till you can find elements.
5. 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).

---

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
}

---

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.