Decrease the probability of getting random item from array same as previous one

Question

Say, I've got an array like

var arr = [1,2,3,4,5,6,7,8,9,10,11,12];

and I wanna get random array item, but later I would like to re-randomize my current item. What is the efficient way to exclude or reduce the chance of getting the same item once again?

Does stuff like this really help:

current != arr[Math.floor(Math.random() * 12)] ? current = arr[Math.floor(Math.random() * 12)] : arr[Math.floor(Math.random() * 12)];

I mean, would it recalculate random array index each time or just link to the same value? What is a better way?

If your generated random number is same as previously generated random number, then generate another random number — The Guest, May 11 '15 at 20:11
Do you want to EXCLUDE previous items or REDUCE the chances of getting the same? The solution would be dependent on your requirements. — Moob, May 11 '15 at 20:12
@Mood I really want to exclude, but if it's impossible or too greedy reduce would be fine too — tristantzara, May 11 '15 at 20:18
Your posted code would have no effect. You have three independent calls to `Math.random()` the outcome of the first having no effect on the others. — James Montagne, May 11 '15 at 20:19
not sure of your Q, but you could use a double array: [1,1,2,2,3,3,...] — JMP, May 11 '15 at 20:21
@TristanTzara http://stackoverflow.com/questions/30176763/javascript-decrease-the-probability-of-getting-random-item-from-array-same-as#comment48460244_30177094 Is requirement to randomize items within `arr` "in place" ; without removing or repeating items within `arr` ? — guest271314, May 11 '15 at 20:38
Are you looking for [this](http://stackoverflow.com/a/11809348/1048572), which prevents duplicates/repetitions entirely, or do you only want to avoid get an element twice in a row? — Bergi, May 11 '15 at 20:39
@Bergi I want just to avoid getting same items in a row, preventing reptitions entirely is not what I want — tristantzara, May 11 '15 at 20:43

score 2 · Answer 1 · edited May 11 '15 at 23:00

2

If you can keep array unsorted: (if not, you can use array which only contains indices of elements in first array)

var array = [ ... ];
var len = array.length;

function getRandomItem(){
    if (len <= 0) len = array.length;
    var item = Math.floor(Math.random()*len--);
    var x = array[item];
    array[item] = array[len];
    array[len] = x;
    return array[len];
}

Idea behind is to exclude already dispatched items by placing them outside of item fetching range. Function getRandomItem() will not return same item twice until all other elements also will be returned.

Following modification will only prevent function to return same element which was returned during previous call, as requested.

var array = [ 3, 1, 4, 5, 9, 2, 6, 8, 7 ];
var len = array.length-1;

function getRandomItem(){
    if (len == 0) return array[0];
    var item = Math.floor(Math.random()*len);
    var x = array[item];
    array[item] = array[len];
    array[len] = x;
    return array[len];
}

document.write("Starting array: " + array + "<br/>");
document.write("Selected value: " + getRandomItem() + "<br/>");
document.write("Resulting array: " + array);

Also see Fisher–Yates shuffle

edited May 11 '15 at 23:00

jzheaux

7,042
3
22
36

answered May 11 '15 at 20:30

weaknespase

1,014
8
15

Actually I don't need to permanently ban items that have already been picked, wanna just not to get two same items in a row – tristantzara May 11 '15 at 20:35
updated answer with modification. You can also tune it to return "at least N unique items". – weaknespase May 11 '15 at 20:49
For your second example, I believe the if (len = 0) should be if (len == 0). Also, it is not true that you want to pick between indices 0 and length - 2, leaving the last index out (the one you don't want to pick again)? In this case, wouldn't it be var item = Math.floor(Math.random()*(len - 1)); – jzheaux May 11 '15 at 22:09
Nm, answered my own question. I missed the "- 1" on line 2. :) – jzheaux May 11 '15 at 22:20
A more generalized version of the fisher Yates shuffle is format preserving encryption FYI. Basically, encryption will give you a shuffle without repeats guaranteed, and you can choose your needs of speed vs quality by choosing your encryption algorithm (or crafting your own with something like a feistel network). The encryption key is your shuffle seed. Oh and BTW you don't have to actually store or shuffle any items, you just encrypt the index to get the item at that index, then increment the index. – Alan Wolfe May 12 '15 at 01:52

Mostafa Talebi · Answer 2 · 2015-05-11T20:26:39.950

I think the best solution is to put a while loop to check if the value is similar to the previous one or not.

var arr = [1,2,3,4,5,6,7,8,9,10,11,12];

Then you write:

   var last_generated_value = null;
   var val = Math.random();
   val = Math.floor(val * 12);

   while(last_generated_val == val)
   {
       val = Math.random();
       val = Math.floor(val * 12);
   }

   last_generated_value = val;

Though you may put the above code block in a parent loop or a function to generate a concatenated set of values(in your case, number).

mbillard · Answer 3 · 2015-05-11T20:38:11.843

There are so many ways to achieve this. Maybe add a weight to each value and consider it in your random number selection? Then when you get it, reduce its weight. For example:

var weights = {};
var max = 12;

function initializeWeights() {
    var i;

    for (i = 1; i <= max; ++i) {
        weights[i] = 100;
    }
}

function getPseudoRandom() {
    var possible_values = [], i, j;

    for (i = 1; i <= max; ++i) {
        for (j = 0; j < weights[i]; ++j) {
            possible_values.push(i);
        }
    }

    random_index = Math.floor(Math.random() * possible_values.length) + 1;
    random = possible_values[random_index];
    weights[random] = weights[random] - 10;
    return random;
}

initializeWeights()
alert(getPseudoRandom());

Then you just have to figure out what to do when you reach 0. Maybe you can increment all the weights by 100.

score 0 · Answer 4 · answered May 11 '15 at 20:49

Try

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];

var clone = arr.slice();

var res = [];

do {
  res.push(clone.splice(Math.random() * clone.length, 1)[0])
} while (clone.length !== 0);

// do stuff with res
document.write(JSON.stringify(res));

document.write(res[Math.floor(Math.random() * res.length)]);

console.log(arr);

score 0 · Answer 5 · answered May 11 '15 at 20:58

0

perhaps this is ok? It seems to work, but maybe I'm missing some details?

            var current = arr[Math.floor(Math.random() * 12)];
            var prev = current;
            do { current = arr[Math.floor(Math.random() * 12)]; }
            while (current == prev);

answered May 11 '15 at 20:58

tristantzara

5,597
6
26
40

What is requirement ? – guest271314 May 11 '15 at 20:59
@guest271314 not to get two same random array items in a row – tristantzara May 11 '15 at 21:00
Tried http://stackoverflow.com/a/30177394/2801559 ? `res` should be array of random items from `arr` , without duplicates. See at stacksnippets ; could a) select entire array , no duplicates `document.write(JSON.stringify(res));` , or b) single "random" item from array see `document.write(res[Math.floor(Math.random() * res.length)]);`; or c) both – guest271314 May 11 '15 at 21:03
@guest271314 it seems to ban repetitions entirely, what is not what i want – tristantzara May 11 '15 at 21:05
What does _"not to get two same random array items in a row"_ intend to convey about requirement ? Not opposite from _"it seems to ban repetitions entirely"_ ? Is requirement that displayed item not have duplicate, or same item _next to_ previous item; e.g.; `1, 1` ; where item value `1` would be displayed next to next "random" item `1` ? – guest271314 May 11 '15 at 21:07
@guest271314 the opposition between "ban repetitions entirely" and "prevent getting two same items in a row" is that in the first case I want to NEVER get the item that I've already picked in the past (no matter, how many iterations ago), and in the second case, I just want to prevent the item, got on n-th iteration be the same as item, got on (n-1)th iteration, while it's totally fine if it's the same as e.g. on (n-2)th iteration – tristantzara May 11 '15 at 21:11
Still not clear on expected results, here, between _"not to get two same random array items in a row"_ and _"it seems to ban repetitions entirely"_. Application of expected results ? Could simply return randomly sorted array `res` , replace one or more items with items from original array `arr` , setting "duplicate" , if that is requirement – guest271314 May 11 '15 at 21:19

score 0 · Answer 6 · answered May 11 '15 at 21:27

You could randomly shuffle the array using a version of the Fisher-Yates algorithm and then just iterate through it:

var arr = [1,2,3,4,5,6,7,8,9,10,11,12],
    shuffle = function(array) {
        for (var i = array.length - 1; i > 0; i--) {
            var j = Math.floor(Math.random() * (i + 1));
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        return array;
    },
    randomisedArray = shuffle(arr),
    nextItem = function(){
      return randomisedArray.pop();
    };

while(randomisedArray.length>0){
   console.log(nextItem());
}

score 0 · Answer 7 · answered May 12 '15 at 18:12

You can do this with a single calculation:

// Just like before...
var arr = [1,2,3,4,5,6,7,8,9,10,11,12];
// Initialize first random index
var currentIndex = Math.floor(Math.random() * arr.length);

// And now...
function Next() {
     currentIndex = (Math.floor(Math.random() * (arr.length - 1)) +
       1 + currentIndex) % arr.length;
     return currentIndex;
}

// Or if you want the next value...
function NextValue() {
     return arr[Next()];
}

The idea is that you always randomize how many items to advance, with a maximum of (length - 1), and use modulo to truncate the index into the valid range.

Decrease the probability of getting random item from array same as previous one

7 Answers7