Javascript, Array shuffle but keeping a certain distance

Question 1

That's not simple, I must admit. Let's start with some helper functions:

Array.prototype.unique = function() {
    var i = 0, t = 1, l = (this.length >>> 0) - 1;
    for (; i < l; t = ++i + 1)
        while ((t = this.indexOf(this[i], t)) !== -1)
            this.splice(t, 1);
    return this;
};
Array.prototype.count = function(item) {
    var i = 0, t = 0;
    while (i = this.indexOf(item, i) + 1) t++;
    return t;
};
Array.prototype.remove = function(item) {
    var i = this.indexOf(item);
    if (i !== -1) this.splice(i, 1);
    return this;
};

I hope the meaning is clear, even if the code may look obscure. There are polyfill for Array.prototype.indexOf for older browsers (IE8-, basically), too.

Now the code:

function shuffleArray(array, previous) {
    if (!array.length) return array;
    // The list of unique items in the array
    var univals = array.slice().unique(),
        idx, pivot, rest;
    if (previous != null)
        // The array can't start with the previous element
        univals.remove(previous);

    while (univals.length) {
        // We choose an element from the possible ones
        idx = Math.floor(Math.random() * univals.length);
        pivot = univals[idx];
        // We try to shuffle the rest of the array.
        rest = shuffleArray(array.slice().remove(pivot), pivot);
        // If we got a shuffled array, we're done.
        // Else, we remove our pivot element from the possible ones
        if (rest != null)
            return [pivot].concat(rest);
        else univals.splice(idx, 1);
    }
    return null;
}

The usage would be:

shuffleArray(array);

You can add a second optional parameter to make it avoid to start with a certain element. It's used recursively inside the function itself. If you get null, then it's not possible to shuffle the array with the given constraints.

Keep in mind that this algorithm can be optimized. In particular, you you can change it so it's not recursive, but rather iterative and more suitable for larger arrays.

Question 2

Here's an algorithm for adding items one at a time. The basic idea is this:

Get an item you want to add to the list
If the list is empty, just add it
If the list is not empty, then generate an array of all possible positions it can be added to the list
Randomly select one of those possible positions
Check if that position is legal by checking the item currently at that position and the one before it. If it is legal, add it there between the two items you just checked.
If that position is not legal, then remove that position from the array of all possible positions and randomly choose another position. Removing it from the array makes sure you don't try the same illegal position over again
Repeat until you've either found a legal position (so you inserted it there) or until you ran out of possible positions (there's no place to put it because you've check all possible positions)

Working demo: http://jsfiddle.net/jfriend00/5xGV3/

var sourceOfItems = ["apple", "grapefruit", "orange", "lime", "pear", "peach", "apricot"];

function insertNextItem(list, item) {

    // special case an empty items array
    if (list.length === 0) {
        list.push(item);
        return true; 
    }

    // build an array of possible insertion positions
    // items.length + 1 means to add it at the end
    var possiblePositions = [];
    for (var i = 0; i < list.length + 1; i++) {
        possiblePositions.push(i);
    }

    // select random position, see if that is allowed
    // if not, remove it from the possibilities and select a new random position
    while (possiblePositions.length > 0) {
        var randIndex = Math.floor(Math.random() * possiblePositions.length);
        var pos = possiblePositions[randIndex];
        // check if this position is allowed
        if (list[pos] !== item && (pos === 0 || list[pos - 1] !== item)) {
            // position is allowed, insert it and return
            list.splice(pos, 0, item);
            return true;
        } else {
            // was not allowed, so remove this possiblePositions choice
            // and let the loop try again
            possiblePositions.splice(randIndex, 1);
        }
    }
    return false;    
}

function buildList(sourceItems, num) {
    var items = [];
    for (var i = 0; i < num; i++) {
        insertNextItem(items, sourceOfItems[Math.floor(Math.random() * sourceOfItems.length)]);
    }
    return items;
}

function go() {
    var list = buildList(sourceOfItems, 20);
}

For a more general version that can handle any minimum distance, see the jsFiddle here: http://jsfiddle.net/jfriend00/LxWNa/

P.S. When viewing the jsFiddle, it's very interesting to look at the debug console output because it shows you what positions were tried that didn't work and what items could not be inserted in the array because there was no legal spot for it.

Question 3

This will not positively add the item afterward, but will randomly shuffle the array! Maybe it will help inspire a way to only add the index afterward? Hope it helps!

//Shuffles an array randomly
var shuffle = function (arrayinput){
  //loops around shuffling for four times the length of the array
  for(i= 0; i<(4 * arrayinput.length); i++){
    //Math.random generates a pseudo-random number between 0 and 1
    //that multiplied by arrayinput.length gives us a random number between 0 and
    //the array length. Math.floor rounds the number down, so we have a pseudo-random
    //number between 0 and the array length - 1, which is all of the array's indexes.
    var a = arrayinput[Math.floor(Math.random() * (arrayinput.length))];
    //saves the value at index a as var b
    var b = arrayinput[a];
    //deletes the one random value at index a from the array
    arrayinput.splice(a, 1);
    //adds that random value back to the beginning of the array
    arrayinput.unshift(b);
  }
  //returns shuffled array
  return arrayinput;
}