Shuffling an array keeping some elements fixed

Question

The task is simple to understand: how to shuffle an array keeping some elements fixed.

Let us take an example: starting from the array [1, 2, 'A', 3, 'B']. Having both 'A' and 'B' as fixed elements. Therefore the process needs to only randomize the position of all other elements in the array. Thus leaving us with six different possible results:

• [1, 2, 'A', 3, 'B']
• [1, 3, 'A', 2, 'B']
• [2, 1, 'A', 3, 'B']
• [2, 3, 'A', 1, 'B']
• [3, 1, 'A', 2, 'B']
• [3, 2, 'A', 1, 'B']

Elements 'A' and 'B' have not moved!

---

Randomizing an array

This is quite an interesting task. Shuffling an array is quite easy. The simplest is Fisher-Yates' algorithm. It works as follows:

A loop goes over the array and for each element will take a random index that is higher or equal to the current element (and less than the number of elements in the array). Then it will swap those two items. So the current element is now a random element and the loop continues on.

The algorithm can be implemented this way in JavaScript:

/**
 * Original Fisher–Yates forward shuffle algorithm
 * Shuffles the given array
 * @param {Array} `a` an array containing items
 */
const shuffle = a => {
    return a.reduce((l, e, i) => {
        const j = Math.floor(Math.random()*(a.length-i)+i); // j is in [i, a.length[
        [ a[i], a[j] ] = [ a[j], a[i] ];
        return a;
    }, a)
}

I am using shorthand syntax (arrow function) and a nice destructuring assignment to swap two items in the array without needing a temporary variable. Also, I have chosen to use .reduce instead of a simple loop so I can return the object straight away.

---

Solutions

1. fixedAllDifferentShuffle(): all fixed elements are different

After doing some research I stumbled upon another post on Stack Overflow but was for Python. So I replicated the algorithm with JavaScript. It consists of the following steps:

1. memorize the position of the fixed items in a separate array fixed
2. shuffle the given array of element
3. swap the position of the fixed elements in the shuffled array to their original position

Example:

• The initial array is:

  `[1, 2, 'A', 3, 'B']`
  

• the array of indexes of fixed elements fixed will be

  [ ['A', 2], ['B', 4] ]
  

• after shuffling the initial array we would get for example:

  [3, 'A', 'B', 2, 1]
  

• so we will need to make the following swap:

  [3, 'A', 'B', 2, 1]
       ↑    ↑
  

  and

  [3, 'A', 'B', 2, 1]
            ↑      ↑
  

• after making those two swaps, we finally get our shuffled* array

  [3, 1, 'A', 2, 'B']
  

Here's how it is implemented using .reduce and .forEach:

/**
 * Shuffles the array `a` without moving the element which are set to true in `f`
 * All fixed elements must be different from eachothers!
 * @param {Array} `a` an array containing the items' value
 * @param {Object} `f` an array containing the items' state
 */
const fixedAllDifferentShuffle = (a, f) => {
    // memorize position of fixed elements
    fixed = a.reduce((acc, e, i) => {
        if(f[i]) acc.push([e,i]);
        return acc;
    }, []);

    a = shuffle(a);

    // swap fixed elements back to their original position
    fixed.forEach(([item, initialIndex]) => {
        currentIndex = a.indexOf(item);
        [a[initialIndex], a[currentIndex]] = [a[currentIndex], a[initialIndex]];
    });

    return a;
}

For our previous example we would have used like:

fixedAllDifferentShuffle(
  [1, 2, 'A', 3, 'B'],
  [false, false, true, false, true]
);

Note: the algorithm will only work if the fixed elements are all different from one another. This is caused by the fact that for each swap currentIndex is defined by .indexOf which means that it will look for the first element matching item and return its index. Therefore if there are two or more fixed elements which have the same value, the code will not swap them to their initial positions successfully.

---

2. fixedUniqueShuffle(): all fixed elements are equal

This is a simplified case because all fixed objects are equal. It is pretty similar to the previous algorithm. But this time I definitely can't use .indexOf since there are multiple equal elements. I've created .indexesOf and added it to Array's properties.

/**
 * indexesOf method for Array, the counterpart of indexOf
 * returns all indexes of `value` in array `a` or -1 if none are present
 * @param {Array} `a` an array to be searched
 * @param {String} `value` is the string to be searched in `a`
 */
 Object.defineProperty(Array.prototype, 'indexesOf', {
    value: function(value) {
        const indexes = this.reduce((acc, e, i) => {
            if(e === value) acc.push(i);
            return acc;
        }, []);
        return indexes.length === 0 ? -1 : indexes
    }
});

Now I can implement my algorithm:

/**
 * Shuffles the array `a` without moving the element `e` from its positions
 * @param {Array} `a` an array containing the items' value
 * @param {String} `e` the fixed element
 */
const fixedUniqueShuffle = (a, e) => {
    const initialFixedPos = a.indexesOf(e);
    a = shuffle(a);
    const currentPos = a.indexesOf(e);
    initialFixedPos.forEach((initial, i) => {
        const current = currentPos[i];
        [ a[initial], a[current] ] = [ a[current], a[initial] ];
    });
    return a
}

So here calling the function would look like:

fixedUniqueShuffle([1, 2, 'A', 3, 'A'], 'A')

---

3. fixedShuffleIndex(): solves all cases

Now I would like an algorithm that would work for every case. To do that we need to shuffle the indexes of the elements, not the element themselves. Here's how it works:

1. we start by reducing the array of elements into two arrays: the first list.pos contains the index of all non-fixed items, the second list.unfixed contains the non-fixed element's value.

2. we shuffle the array of indexes list.pos

3. change the positions of the non-fixed elements in the initial non-shuffled array with list.pos (i.e. the array of shuffled indexes).

This was the closest I could get to achieving the desired result on all cases.

/**
 * Shuffles the array `a` without moving the element which are set to true in `f`
 * @param {Array} `a` an array containing the items' value
 * @param {Object} `f` an array containing the items' state
 */
const fixedShuffleIndex = (a, f) => {
    list = a.reduce((acc, e, i) => {
        if(!f[i]) {
            acc.pos.push(i);
            acc.unfixed.push(e);
        };
        return acc;
    }, { pos: [], unfixed: [] });

    list.pos = shuffle(list.pos);

    return a.map((e, i) => {
        return f[i] ? e : list.unfixed[list.pos.indexOf(i)]
    })
}

The algorithm would work for:

fixedShuffleIndex(
  [1, 2, 'A', 3, 'B'],                   // different and unique
  [false, false, true, false, true]
);

or

fixedShuffleIndex(
  [1, 'A', 'A', 3, 'B'],                 // different with multiplicity
  [false, true, true, false, true]
);

or even

fixedShuffleIndex(
  [1, 2, 'B', 3, 'B'],                   // unique with multiplicity
  [false, false, true, false, true]
);

What do you think of the algorithms? Are there any things that could be improved? Do you have another way of going about solving this problem?

Answer 1

I was a bit surprised by your "progressing" reasoning, because what immediately came into my mind was a general simple solution, whatever the fixed elements are.

The steps are as following:

• make a temporarily reduced array with the not-fixed elements and immediately shuffle it (here it's not far from your final method)
• return this array where fixed elements are re-inserted at their right place

I think this way is a bit simpler, and probably faster (doesn't recreate the whole final array).

Here is a working example:

const shuffle = a => {
  return a.reduce((l, e, i) => {
    const j = Math.floor(Math.random()*(a.length-i)+i); // j is in [i, a.length[
    [ a[i], a[j] ] = [ a[j], a[i] ];
    return a;
  }, a)
};

const fixedShuffleIndex = (a, f) => {
  w = shuffle(
    a.reduce(
      (acc, e, i) => {
        if (!f[i]) {
          acc.push(e);
        }
        return acc;
      },
      []
    )
  );
  return f.reduce(
    (acc, e, i) => {
      if (e) {
        acc.splice(i, 0, a[i]);
      }
      return acc;
    },
    w
  );
}

console.log(fixedShuffleIndex(
  [1, 2, 'A', 3, 'B'],
  [false, false, true, false, true]
));
console.log(fixedShuffleIndex(
  [1, 'A', 'A', 3, 'B'],
  [false, true, true, false, true]
));
console.log(fixedShuffleIndex(
  [1, 2, 'B', 3, 'B'],
  [false, false, true, false, true]
));

Answer 2

A is an array where 'x' are fixed elements

A = [0,'x',2,3,'x',4,5] 


console.log(fixedShuffle(A,'x'))

prints

[2,'x',0,4,'x',5,3]

Solution

I don't know it's good from probabilistic view point. i.e. elements are equally randomized for large iterations.

I did a little tweak on Fisher-Yates Algorithm

let fixedShuffle= (array,peg) => {
        var currentIndex = array.length, temporaryValue, randomIndex;

        // While there remain elements to shuffle...
        while (0 !== currentIndex) {

            // Pick a remaining element...
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex -= 1;

Don't shuffle if index hits the peg

if(array[currentIndex]===peg || array[randomIndex]===peg) continue;

            // And swap it with the current element.
            temporaryValue = array[currentIndex];
            array[currentIndex] = array[randomIndex];
            array[randomIndex] = temporaryValue;
        }
        return array;
    }

Answer 3

If you prepare an array of indices of swappable items you can easily shuffle them with a reversed Fisher-Yates algorithm on indices.

Suppose the array to shuffle has 7 items: a = [20, '-', '-', 23, 24, '-', 26]
and f = [1, 2, 5] are fixed positions.
Then prepare pos = [0, 3, 4, 6], which is 'all indices of a except those in f'.
Finally do F-Y to shuffle items at positions listed in pos:

    for each i from pos.length-1 down to 1
        generate random j between 0 and i (inclusive)
        swap a[pos[j]] with a[pos[i]]