Vector shuffling — A JavaScript functional implementation

The reshuffling of the elements of a vector can be obtained with two simple and very similar algorithms:

the vector is traversed in one direction (can be indifferently left to right or right to left) and each element is exchanged with an element chosen at random respectively among the successive elements of the vector (Durstenfeld’s algorithm) or among the previous elements (inside-out algorithm)¹.

Assuming to scan from left to right, the following image illustrates the difference between the two algorithms (targets positions of red arrows are chosen randomly)

Both algorithms are suitable for implementations that mutate the starting vector. Here below a snippet that uses a declarative programming style (well, an if should exclude the case i equal to j but I have avoided it to keep the code more similar to the functional version):

Declarative implementation. To switch between the two algorithms comment our line 3 or 4

Traversal functions forEach and reduce (used below) take a function as argument and apply it to all element of a vector. The (common) arguments of the inner functions are: e is the current element; i the current index; v the source vector.

Only the inside-out algorithm is suitable for a functional implementation because if we distinguish the source vector (that will not mutate) and the resulting one, it is evident that at a given moment the resulting elements, subsequent to the current position, are not yet available (therefore Durstenfeld’s algorithm is not applicable).

There are two main traversal functions that produce a new value: the map function and the reduce function.

map creates a vector of transformed element but at each step the elements already transformed are not accessible.

reduce creates a new result accumulated during the traversal. The result can be a primitive value (number, string, boolean), or an object (Object, Array, Set, …). At each step the argument function (the reducer) takes as first parameter, in addition to the attributes defined before, the current accumulated value. A second reduce argument defines the initial value of the accumulator.

From the previous picture is clear that the result is not a simple mapping: each iteration also changes one of the previously calculated values. The only possibility is to use the reduce function.

The functional version will be obtained through successive steps starting from the declarative version previously introduced.

The first step consists of transforming the declarative function into a pure function. The original function is encapsulated into a function that creates a new vector and returns it as result.

The second step consists in the introduction of the reduce function:

• the external function is removed
• the forEach is replaced by reduce
• the resulting vector becomes the first argument of the reduce function
• the initial value of the result becomes the second parameter of the reduce function.

Well it is a pure function even if internally it uses mutations.

Nevertheless there are things that are not evident:

1. the if at line 6 is needed because left part of the assignment creates the element at position i, but in case j is equal to i the right element is not yet available (it shall be created by the left part).
2. line 7 works differently in the case i is equal to j: the left part of the assignment creates the vector element.

The third step consist of transforming the reducer function into a pure function. It has less to do with human-machine communication because it provides a less efficient implementation. It concerns the communication between humans and provides an intuitive and immediate understanding of behaviors, avoiding the imperative complications.

In lines 5, 6 the three dots operator removes the vector structure around vector elements: …[1,2,3,4] produce 1,2,3,4. But the released elements cannot live alone: they must be reassembled in a new vector, possibly with other elements (the external square brackets of lines 5, 6).

Here below line 5 is compared with the picture that illustrate the functional algorithm (focusing on the last step where i is 3, j is 1 and e is the yellow square):

So, when the impact on performance is irrelevant, pure functions are the most expressive way to communicate with other readers of the code, a means to communication with humans.

Testing the snippets

Given a vector of n elements (and assuming them all different) the number of possible reshuffles coincides with the number of permutations of n elements: n!

Taking into account the previous statement, we can carry out a rough check of the goodness of the algorithms by shuffling several times (e.g. 1000) the same vector (no longer than 4–5 elements) and verifying that the frequencies of the permutations are more or less equal.

A more precise check should give a statistical meaning to the expression ‘more or less equal’ (but this is another story: it requires big numbers. You can try with a vector containing 6 or 7 elements and with at least 50000 scrambles. Having this data it is possible to calculate the mean and deviation values of frequencies).

In the previous code

• The count function is a functional replacement of the range loop for(i=0;i<n;i++). It creates a vector of n null elements.
• The reducer is a pure function (it does not mutate the acc but returns a new object).
• The three dots operator removes the object structure releasing the properties (like for vectors, where it releases the elements).
• line 7 can be understood remembering that objects are kind of hashMaps and object properties are strings: obj.prop=foo is equivalent to obj[‘prop’]=foo

To test, you can copy and run the code snippets in the console of your browser (activated by F12 key). Do not copy the const keyword otherwise you cannot re-declare functions and objects

The theoretical frequency of each permutation is given by the number of tests divided by the number of permutations. In our case 1000/24 = 41. 66….

Cycles

In both shuffling algorithms,if, at each iteration, the possibility to keep the current element in its position is excluded (it is sufficient to remove respectively the lower or the upper bound of the range of random positions) the output is a cycle of n elements. The ‘inside-out’ algorithm modified in this way is known as Satollo’s algorithm¹.

Intuitively, a cycle is a permutation in which no vector element remains in its initial position. The total number of cycles is (n-1)!

However for cycles there is still something that is not yet clearly declared: why the first element is inserted in the first position of the resulting array (it seems to contradict the definition)? Well because the second element, that cannot be inserted in the second position, is forced to be exchanged with the first element. It is possible to make all this evident in the code.

[1]: Wikipedia contributors. (2019, November 9). Fisher–Yates shuffle. In Wikipedia, The Free Encyclopedia. Retrieved 08:31, November 23, 2019, from https://en.wikipedia.org/w/index.php?title=Fisher%E2%80%93Yates_shuffle&oldid=925384088