Shuffles Random Numbers with no repetition in Javascript/PHP

Question

I've searched through some of the answers here but it doesn't seem the thing that I needed or I just don't know how to apply it though.

I haven't started any codes and I'm only thinking on how to do it and I have no idea how to do it. I need your help guys.

Let's assume that I have an array which consists of these values below

[1,2,3,4,5,6,7,8,9]

And I need to shuffle it without repeating the position of each numbers of the last result. so it would probably like

[5,3,9,6,2,8,1,4,7]

if I shuffle it again it would be like

[4,7,2,1,8,3,6,9,5]

And so on.

Well I don't know if there' any relevance to it but, would rather not to use rand() though. Any solution for this stuff?

Do you want to create every possible combination? If not just shuffle the array, compare it to each of the already shuffled arrays. if it matches reshuffle it, if not add it. — Imperative, Feb 21 '13 at 13:47
In php you can use function `shuffle(&$array)`. Pass an array - and it will shuffle it for you. You can't guarantee constant non-repeat, but you're very-very unlikely to get repeated results on two subsequent calls. — Aleks G, Feb 21 '13 at 13:48
you can also split the array into smaller array, shuffle those, and recreate the large array from the smaller arrays in a random order. So you end up with [2,3,1][6,5,4][8,9,7] and then maybe [6,5,4][2,3,1][8,9,7] which when merged becomes : [6,5,4,2,3,1,8,9,7] — Husman, Feb 21 '13 at 13:51
so you don't want the numbers to repeat in the same position for how many iterations/suffles? — Hugo Alves, Feb 21 '13 at 13:56
@Bergi from what i understand he doesn't what each number to repeat the same/last position where it was for n suffles. so it's not a duplicate — Hugo Alves, Feb 21 '13 at 13:59

Tony Stark · Accepted Answer · 2013-02-21T13:55:54.117

2

Try this,

$count = 15;
$values = range(1, $count);
shuffle($values);
$values = array_slice($values, 0, 15);

OR

$numbers = array();
do {
   $possible = rand(1,15);
   if (!isset($numbers[$possible])) {
      $numbers[$possible] = true;
   }
} while (count($numbers) < 15);
print_r(array_keys($numbers));

may this help you.

edited Feb 21 '13 at 13:55

answered Feb 21 '13 at 13:50

Tony Stark

8,064
8
44
63

score 1 · Answer 2 · answered Feb 21 '13 at 14:04

What you want to do is to add elements from your array to another array, randomly, but to ensure that elements are not in the same indexed position. Try this:

$array = [1,2,3,4,5,6,7,8,9];
$new = array();
for($i = 0; $i < $array.length; $i++){
  $rand = $i;
  do {
    $rand = Math.floor( Math.random() * ( $array.length + 1 ) );
  } while ($rand == $i || array_key_exists($rand, $new))
  // Check that new position is not equal to current index
  // and that it doesnt contain another element

  $new[$rand] = $array[i];
}

Not the most efficient, but guaranteed to put elements in non same indices.

Actually, it's quite inefficient and there's a much more elegant solution to ensure `i != j` — Bergi, Feb 21 '13 at 15:01

score 1 · Answer 3 · answered Feb 21 '13 at 14:57

1

You can use the variant of the Fisher-Yates-Shuffle which does biased randomly choose the swapped element and is known as Sattolo's algorithm:

function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * i); // no +1 here!
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    return array;
}

That way, every element is guaranteed to be swapped and not appear in the same position as before.

answered Feb 21 '13 at 14:57

Bergi

630,263
148
957
1,375

@joe: Quite unlikely (or rather, impossible given the algorithm, as long as the array has more than 1 element). Can you make a demonstration of your code (e.g. a fiddle)? – Bergi Feb 03 '16 at 11:56
@joe: you've probably [got a problem with your console output](http://stackoverflow.com/q/23392111/1048572) as you're repeatedly logging the same array. Try [this one](https://jsfiddle.net/4vzy28ke/2/) (`shuffleArray` has not been changed) – Bergi Feb 03 '16 at 12:08
it gives the same results. second log was actually the same [1,2,3], so positions are repeated. – joe Feb 03 '16 at 12:14
@joe Of course the second one can be the same as the original input, it's just guaranteed to be different in all position from the first one. – Bergi Feb 03 '16 at 13:02
1

duh :D i just realised what the problem was. it returns the same array (modifies the original one), therefore the next call will start shuffling something like [3,1,2], which can return [1,2,3] as they're not in the same positions :) – joe Feb 03 '16 at 13:28

Hugo Alves · Answer 4 · 2013-02-21T15:40:45.333

This makes the values of the array not repeat any previous position for n shuffles (i'm using half of the array's size as n, after that i restart the forbidden indexes). At the end a modified this version to make it not repeat the current position.

For this you will have to save a history of all the index where each value of the orignal array has been. To do this i've added a little more complexity to your numbers

var numberArray = [{value:1, unavailable_indexes:[0]},
                   {value:2, unavailable_indexes:[1]},
                   {value:3, unavailable_indexes:[2]},
                   {value:4, unavailable_indexes:[3]},
                   {value:5, unavailable_indexes:[4]},
                   {value:6, unavailable_indexes:[5]},
                   {value:7, unavailable_indexes:[6]},
                   {value:8, unavailable_indexes:[7]},
                   {value:9, unavailable_indexes:[8]}
                  ];

this way you have the number in value and an array of all the positions where it has been. Next we need to run all the array and switch numbers around.

var arrayLen = numberArray.length-1;
$.each(numberArray, function(index, value){
    var newIndex;
    //restart the array when half of the index have been covered or it will take awhile to get a random index that wasn't used
    if(value.unavailable_indexes.length >= numberArray.length/2)
        value.unavailable_indexes = [index];//restart the unavailable indexes with the current index as unavailable
    do{
        newIndex = Math.floor(Math.random()*arrayLen);
    //verify if you can swap the 2 values, if any of them have been on the destination index get another random index
    }while($.inArray(value.unavailable_indexes, newIndex) || $.inArray(numberArray[newIndex].unavailable_indexes, index));


    numberArray[index] = numberArray[newIndex];
    numberArray[newIndex] = value;
})

after all the array has been moved around you need to save the positions where they landed

$.each(numberArray, function(index, value){
   value.unavailable_indexes.push(index);
}

EDIT: if you just want to prevent it from just repeating the previous position then make unavailable_indexes hold the last position it was in and replace the do{...}while() with:

do{
    newIndex = Math.floor(Math.random()*arrayLen);
}while(newIndex != value.unavailable_indexes)

and the last method would look like:

$.each(numberArray, function(index, value){
   value.unavailable_indexes = index;
}

score 0 · Answer 5 · answered Mar 02 '17 at 16:53

I just came up with the following code, to combat a problem I was having where sometimes my randomly shuffled array would end up in it's original order (was it too random, or not random enough?).

How it works, it loops over a while loop until the $isDifferent variable becomes true, which can only happen if the arrays do not match. This perhaps may work similarly to the Fisher-Yates method, although when I tried that, I still ended up with matching arrays on occasion.

This solution is written in PHP but could easily be converted to JavaScript.

guaranteedShuffle($array){
    $isDifferent = false;
    while(!$isDifferent){
        $arrayCopy = $array;
        shuffle($arrayCopy);
        if($array !== $arrayCopy){
            $isDifferent = true;
        }
    }
    return $arrayCopy;
}

Usage:

$array = ['1','2']; 
$shuffled = guaranteedShuffle($array);

score -1 · Answer 6 · edited May 23 '17 at 11:46

-1

You can shuffle using Fisher Yates Shuffle

function fisherYates ( myArray ) {
var i = myArray.length, j, tempi, tempj;
if ( i == 0 ) return false;
while ( --i ) {
 j = Math.floor( Math.random() * ( i + 1 ) );
 tempi = myArray[i];
 tempj = myArray[j];
 myArray[i] = tempj;
 myArray[j] = tempi;
}
}

See this reference

edited May 23 '17 at 11:46

Community

1
1

answered Feb 21 '13 at 13:50

Dineshkani

2,899
7
31
43

No. That might come out with the last result. – Bergi Mar 25 '13 at 14:57

Shuffles Random Numbers with no repetition in Javascript/PHP

6 Answers6

Linked

Related