0

I've been trying to do this for a long time but have every time failed. I have var rand = Math.floor(Math.random() * 5); and log.push(rand);. And to make sure that it doesn't repeat any values, I try:

function dontRepeat() {
    var g = 0;
    for (var i = 0; i < log.length; i++) {
        if (log[log.length - i] == rand) g++;
        if (g > 1) {
            rand = Math.floor(Math.random() * n);
            dontRepeat();
        }
    }
}

Please help me find out what is wrong.

David G
  • 94,763
  • 41
  • 167
  • 253
  • Are you just trying to create an array of unique random numbers? Or is it a long living array that you occasionally add elements to? What's the use case? – Sergio Tulentsev Jan 30 '12 at 21:52
  • possible duplicate of [Generating unique random numbers (integers) between 0 and 'x'](http://stackoverflow.com/q/8378870/938089?generating-unique-random-numbers-integers-between-0-and-x) – Rob W Jan 30 '12 at 21:54
  • @Jivings What? jQuery? Why do you want to use jQuery for creating a JavaScript array of unique random numbers? – Rob W Jan 30 '12 at 21:54
  • also related, http://stackoverflow.com/q/962802/7613 – Andrew Jan 30 '12 at 21:55
  • @RobW It defines an inArray() function. – Jivings Jan 30 '12 at 22:09
  • How big is `n`? Also, how big is `log.length` in comparison to `n`? Solutions that use `indexOf` or similar to test for numbers already added will slow as you near `n` numbers due to having to guess all but the last few numbers. If both `n` and `log.length` are large you are doing a lot of searching. See answer below using Ficher-Yates. – Brett Pontarelli Jan 30 '12 at 22:47

5 Answers5

1

Why not just do this:

function unique_randoms(length, maximum) {
  var numbers = [];
  var test;

  for (var i = 0; i < length; i++) {
    do {
      test = Math.floor(Math.random() * maximum);
    } while (numbers.indexOf(test) != -1);

    numbers.push(test);
  }

  return numbers;
}

Demo: http://jsfiddle.net/ZSE2w/

You don't really need to do recursion. Also, make sure length <= maximum.

Blender
  • 289,723
  • 53
  • 439
  • 496
0

Why don't you just store the values in log inside a dictionary/set and keep checking for every new value that you are pushing whether it's already inserted in the dictionary/set or not. If there aren't too many values you aren't wasting that much space by this solution.

Sid
  • 7,511
  • 2
  • 28
  • 41
0

Keep track of the already used numbers as properties of an object (in which case you might benefit from constant-time property lookup), (untested):

function getNonDuplicateRandoms(n, max) {
  var used={}, numbers=[], rand, i;
  if (n > max) throw new Error("n > max");
  for (i=0; i<n; i++) {
    do {
      rand = Math.floor(Math.random() * max);
    } while (used[rand]);
    numbers.push(rand);
    used[rand] = true;
  }
  return numbers;
}
maerics
  • 151,642
  • 46
  • 269
  • 291
0

You can get a duplicate free list by first making an ordered array:

A = [];
for(i=0; i<n; i++) A[i]=i;

Then shuffle the array:

for(i=0; i<n; i++) {
  r = Math.floor(Math.random() * (i + 1));
  swap = A[i];
  A[i] = A[r];
  A[r] = swap;
}

Now take what you need up to n. If n is really big this will use a lot of memory, in which case it may be more efficient to use an indexOf approach to test for what has already been used. However, this method is slow and get slower as the number of items you need get close to n.

Brett Pontarelli
  • 1,718
  • 15
  • 29
-1

The most obvious solution - keeping a log of all results and keep randomly generating numbers - is not effective because it is random, and for all you know, it could randomly generate the same numbers as you already have generated for close to eternity (very unlikely, but still).

The easiest and most effective way, at least for managable ranges of possibilities, is therefore to make an array of all possible choices:

var choices = [1, 2, 3, 4];

Then shuffle the array using Array.sort():

// Randomization function, to sort randomly
var random_function = function(x, y) { return 0.5 - Math.random(); }

choices.sort(random_function);

Or, in one line:

choices.sort(function(x,y) { return 0.5 - Math.random(); }

Finally, slice the array to only get n results:

var result = choices.slice(0, n);
Frxstrem
  • 38,761
  • 9
  • 79
  • 119