4

Is there any method apart from array splicing that I can use to generate a random number between two numbers without repeating at all until all the numbers between those two numbers have been generated? Shuffling techniques or any other array methods apart from splicing would be extremely helpful.

Ronophobia
  • 349
  • 3
  • 16

3 Answers3

2

First we use the fisherYates implementation (credit goes to @ChristopheD) and extend the array prototype to have a shuffle function available

function arrayShuffle () {
   var i = this.length, j, temp;
   if ( i === 0 ) return false;
   while ( --i ) {
      j = Math.floor( Math.random() * ( i + 1 ) );
      temp = this[i];
      this[i] = this[j]; 
      this[j] = temp;
   }
}

Array.prototype.shuffle =arrayShuffle;

var numbers = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
numbers.shuffle();

Now with the use of the pop method we get a number from our seed until it is empty

numbers.pop(); //returns a number

To make sure we have an array filled with numbers in the range of start and end we use a simple loop to create our seed.

var start = 1;
var end = 5;
var numbers = new Array();
for (var i = start; i <= end; i++) {
    numbers.push(i);
}

here is a sample on jsfiddle

UPDATE: put fisherYates algo to shuffle more efficient

Community
  • 1
  • 1
MatthiasLaug
  • 2,924
  • 6
  • 28
  • 43
  • 2
    This is a bad (non-uniform) shuffling algorithm. To see that it cannot be an uniform shuffling just consider that there are `N**N` equally probable shufflings while the number of permutations of `N` elements is `N!` and that in general `N**N` is not an exact multiple of `N!`. – 6502 May 24 '13 at 05:50
  • This is not the correct way to shuffle. Look up Fisher-Yates shuffle. You can shuffle each member only LATER on in the list. This way you get n! possible permutations, which is the correct number to hit each exactly once. – Patashu May 24 '13 at 05:56
  • dear lord, it should not been an academic solution. But for gods sake I put a more efficient shuffling algorithm :) – MatthiasLaug May 24 '13 at 06:00
  • 2
    @MatthaisLaug Your shuffling algorithm was incorrect. As in, it was biased. As in, it did not pick all shuffles equally often. That's what we're complaining about, because lack of correctness is very bad :) – Patashu May 24 '13 at 06:03
  • @MatthiasLaug: you don't get it: it's not about efficiency but correctness. This shuffling algorithm is not "fair". It's not as bad as leaving always the first three elements in the initial places, but it's not correct either. Given that it takes almost nothing to fix it to a correct algorithm (see link) using this code is a bad idea. – 6502 May 24 '13 at 06:05
  • But wait if I want to find a number between and including two numbers and I fill an array up with these numbers then will every consecutive call of the Fisher-Yates shuffle function on the array return a different combination of the array contents? Like will all the combinations possible be satisfied before a combination can repeat? Because that is sort of what I was looking for :/ – Ronophobia May 24 '13 at 06:12
  • 1
    the fisterYates `is an algorithm for generating a random permutation of a finite set—in plain terms, for randomly shuffling the set` but it might happen, that you are getting the same permutation once again, before all permutation have shown up. If you want to avoid that, you need to provide an array of array to the shuffle method to check if the new shuffled array has not yet been used – MatthiasLaug May 24 '13 at 06:15
  • Yeah right? While I don't doubt the efficiency of the algorithm,the chances of the same permutation showing up is still significantly high from what I have experienced. – Ronophobia May 24 '13 at 06:18
  • @MatthiasLaug Yes I will probably have to do something like that. Thanks. – Ronophobia May 24 '13 at 06:20
0

What I usually do when dealing with smaller arrays is sorting the array by random:

yourArray.sort(function() { return 0.5 - Math.random() });
Max Fahl
  • 818
  • 9
  • 19
-1

Try this http://jsbin.com/imukuh/1/edit:

function randRange(min, max) {
  var result = [];
  for (var i=min; i<=max; i++) result.push(i);
  return result.map(function(v){ return [Math.random(), v] })
    .sort().map(function(v){ return v[1] });
}

console.log(randRange(1,5));
// [4, 3, 1, 5, 2]
// [3, 5, 2, 4, 1]
// [1, 5, 2, 3, 4]
// [3, 2, 5, 1, 4]
// ...
elclanrs
  • 92,861
  • 21
  • 134
  • 171