1
\$\begingroup\$

Is the following procedure good for shuffling data in general (not just for JavaScript)?

function Shuffle(array) {
  var temp = null,
    len = array.length - 1,
    rnd = null;
  for (var i = len; i > 0; i--) {
    // Generate a random number in which does not exceeds the length of array.
    rnd = Math.floor(Math.random() * len);
    // Assign last item in array to "temp" variable.
    temp = array[len];
    // Assign a random number to last item in array.
    array[len] = array[rnd];
    // Assign value of "temp" variable which may we added previously to the array last random item which has been generated previously. 
    array[rnd] = temp;
  }
  return array;
}

// Implementation
var arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];
document.getElementById('result').innerHTML = Shuffle(arr);
<div id="result" style="font-size:25px;"></div>

\$\endgroup\$
1
\$\begingroup\$

Your algorithm is a variant of Fisher-Yates shuffle, and it's a good algorithm to shuffle a collection. A more common form is instead of using the last element to swap, you could have used the decreasing index i to swap, like this:

  for (var i = len; i > 0; i--) {
    rnd = Math.floor(Math.random() * len);
    temp = array[rnd];
    array[rnd] = array[i];
    array[i] = temp;
  }

It doesn't matter much though, your version is fine too.

Something to improve is a bit cosmetic: it would be better to name your function with lowercase letters, shuffle, because it's customary to start with a capital letter only functions that are used to create objects with the new keyword.

Lastly, this is a bit tedious to type:

var arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];

You could use this shorter form instead:

var arr = "abcdefghi".split("");
\$\endgroup\$
  • \$\begingroup\$ I thank you for your review and opinion too. Regarding to your first code and this portion array[rnd] = array[i]; and using array[i] instead of array[rnd] it will generate some similar numbers. \$\endgroup\$ – Lion King Dec 26 '16 at 22:42
  • \$\begingroup\$ What do you mean? \$\endgroup\$ – janos Dec 26 '16 at 22:47
  • \$\begingroup\$ I think you made a mistake when copying. The loop I gave you is to replace the loop in your code, with nothing else changed. It should not produce the kind of output you posted in the comment. \$\endgroup\$ – janos Dec 26 '16 at 22:55
  • \$\begingroup\$ I am sorry, that mistake from me (when copying code). \$\endgroup\$ – Lion King Dec 26 '16 at 22:59
1
\$\begingroup\$

Not at all random

The short answer is NO it is a terrible way to shuffle and not at all random. You have a bias of 85%+, this value should be < 1% to be considered random, and 100% being no change.

Even the improvement suggested by janos does not help much reducing the bias to ~26%

Only the first item swapped looks random, but that's because it get swapped more often than any other item.

Going with the better version for now.

The logic?

For each item swap it with a random position.

function Shuffle (array) {
    var temp, rnd, rnd1, len, i;
    len = array.length;
    for (i = 0; i < len; i += 1) {
        rnd = Math.floor(Math.random() * len);
        temp = array[i];
        array[i] = array[rnd];
        array[rnd] = temp;
    }
    return array;
}

Swap the first item with a random position. The first item has a 8 in 9 chance of being above 1, so there is a good chance it will be swapped with a random pos again, but the item that moved to 1 will only have the random selection chance to be moved again. As soon as you have a system in which starting position changes the odds of being shuffled you add a bias to the shuffle.

Even if the result looks random to the eye they are not so in reality.

Testing for random

To test you need to find out how often each item ends up in a particular position after each shuffle (starting from the same pos each time)

Example start with ordered 123456789 array and a count array, then shuffle, in the count array add one for the position the first item landed in.

// counting position of item 1 after each shuffle
start...> 123456789
shuffle.> 352197468
             ^
count...> ---1-----  // 1 in pos 3 count[3] = 1

start...> 123456789
shuffle.> 746352198
                ^
count...> ---1--1--  // 1 in pos 6 count[6] = 1 

start...> 123456789
shuffle.> 752146398
             ^
count...> ---2--1--  // 1 in pos 3 again count[3] is now 2

// do 1,000,000 times or more

Over time the difference from the lowest count and the highest count for any item should slowly approch 0%.

Distribution test results

enter image description here

The test is of 1,000,000 shuffles each starting with the same array. As you can see the first item A has a good random distribution with the difference between the highest and lowest position of 1.06%. But all others had terrible bias. If it were gambling this level of bias would bankrupt a tote in a few dozen shuffles.

Look at the center one E, it is 27% less likely to be in its starting position than in the position one down, and approx > 50% chance of being in position b,c,d.

To improve.

Using the algorithm you have can get better results by just shuffling the array more than once. This of course increases processing time.

If we look at the distribution range between the lowest position count and the highest for each item, we can see that the number of shuffles make a big difference. Just by shuffling twice reduces the distribution of the last 8 items from the 27% to < 2%, but compared to the first item the distribution is still not even across all items. Shuffling 8 times brings all to under 1% distribution, but the problem remains that the first item will alway have a distribution that is lower than all the other items.

Remove select bias

You can instead randomly select both items for the swap each time and shuffle the array 4 times. This reduces the distribution of all items to around 1% for 1,000,000 shuffles.

function Shuffle (array) {
    var temp, rnd, rnd1, len, i;
    len = array.length;
    for (i = 0; i < len * 4; i+= 1) {
       rnd = Math.floor(Math.random() * len);
       rnd1 = Math.floor(Math.random() * len);
       temp = array[rnd];
       array[rnd] = array[rnd1];
       array[rnd1] = temp;
    }
    return array;
}

But it is still not the best.

There is only one way to shuffle.

The only way to shuffle and be as random as the random number generator you are using is by random pick. You create a new empty array, then randomly select and remove am item from the original array and push it onto the new one.

function shuffle(array){
    var temp = [...array]; // create a copy of the array
    array.length = 0; // empty the original array
    while(temp.length > 1){
         array.push(temp.splice(Math.floor(Math.random() * temp.length), 1)[0]);
    }
    array.push(temp[0]);  // add the last item
    return array;
}

You only need to touch each item once (excluding the copy if you do not need the array shuffle to be in place) and there is no bias inherent in the function. The only limiting factor to the randomness is the random number generator itself.

\$\endgroup\$
  • \$\begingroup\$ Fisher Yates is pretty widely accepted. That is use by all if not most of the poker sites. \$\endgroup\$ – paparazzo Dec 27 '16 at 3:10
  • 1
    \$\begingroup\$ @Paparazzi That is what the last part of my answer is, I call it random pick. The OP is not using the FishYat method nor is the other answer as they are not adjusting the random selection range after each swap, i thought they were both just doing a brute force shuffle, without the brute (lots of iterations) that is. \$\endgroup\$ – Blindman67 Dec 27 '16 at 4:10
  • \$\begingroup\$ That is not Fisher Yates \$\endgroup\$ – paparazzo Dec 27 '16 at 4:21
  • \$\begingroup\$ @Paparazzi Yes it is, pick & remove random item from original list, add to new list, repeat until original list is empty. en.wikipedia.org/wiki/… \$\endgroup\$ – Blindman67 Dec 27 '16 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.