How can I generate a random number within a range but exclude some?

Basically I pick a random number between 0-24:

Math.floor(Math.random() * myArray.length); // myArray contains 25 items

Lets say it comes out to be 8. Now I want to get another number in the same range 0-24 but this time, I do not want an 8. The next time, I might roll a 15. Now I want to roll again but I don't want an 8 or 15. The way I am handling this now is by using do while loops and if the number comes out the same, I just reroll.

This is a small portion of my homework and I, in fact, have it working to meet all the requirements so I guess you could say this is for my own personal benefit so I can write this properl开发者_StackOverflow社区y and not end up on "the daily wtf".

Set an array with all the values (this is only a valid option if you're only doing small numbers, like the 25 in your example), like this:

var array = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24];

then, pick a random number between 0 and the array length:

var num = Math.floor(Math.random() * array.length);

remove that index number from the array:

var roll = array.splice(num, 1);

Javascript splice() removes indexed items from an array and returns the item(s) as an array. Perfect for your use.

Grab the first index from the roll, since we only cut 1 out anyway:

var yourNumber = roll[ 0 ];

Keep doing for as many rolls as you want. Also, you might want to store the original array as a copy so that you can "reset" the numbers easily.

This is easy guys. You do not want recursion for this one. These answers are really bad. Ideally you do not want to hardcode the array, either.

function getRandomWithOneExclusion(lengthOfArray,indexToExclude){

  var rand = null;  //an integer

    while(rand === null || rand === indexToExclude){
       rand = Math.round(Math.random() * (lengthOfArray - 1));
    }

  return rand;
}

now use the value returned from the above function to choose an element from whatever array you want, just like so:

var arr = [];
var random = getRandomWithOneExclusion(arr.length,5);  //array has length x, we want to exclude the 5th element
var elem = arr[random];

that's it. if you wanted to exclude more than value, then you would have to make this more sophisticated, but for excluding one value, this works well. A recursive solution for this is overkill and a bad idea.

I haven't tested this, but to exclude more than one element, try this:

function getRandomWithManyExclusions(originalArray,arrayOfIndexesToExclude){

   var rand = null;

   while(rand === null || arrayOfIndexesToExclude.includes(rand)){
         rand = Math.round(Math.random() * (originalArray.length - 1));
    }
     return rand;
  }

The above method does not sound too different from the OP's original method. This method works properly because it does not sample in a biased way from the array.

Suppose you need to choose a random number from the range 1...5 and exclude the values 2, 4 then:

• Pick a random number from the range 1...3
• Sort excluded number list
• For each excluded number less than/equal to the random number: add one to the random number

function getRandomExcept(min, max, except) {
  except.sort(function(a, b) {
    return a - b;
  });
  var random = Math.floor(Math.random() * (max - min + 1 - except.length)) + min;
  var i;
  for (i = 0; i < except.length; i++) {
    if (except[i] > random) {
      break;
    }
    random++;
  }
  return random;
}

/*
 * Test iterations. Make sure that:
 * excluded numbers are skipped 
 * numbers are equally distributed
 */
(function(min, max, except) {
  var iterations = 1000000;
  var i;
  var random;
  var results = {};
  for (i = 0; i < iterations; i++) {
    random = getRandomExcept(min, max, except);
    results[random] = (results[random] || 0) + 1;
  }
  for (random in results) {
    console.log("value: " + random + ", count: " + results[random] + ", percent: " + results[random] * 100 / iterations + "%");
  }
})(1, 5, [2, 4]);

This is example without recursion and without creating a huge array:

const getRandomWithExclude = (min, max, excludeArray) => {
  const randomNumber = Math.floor(Math.random() * (max - min + 1 - excludeArray.length)) + min;
  return randomNumber + excludeArray.sort((a, b) => a - b).reduce((acc, element) => { return randomNumber >= element - acc ? acc + 1 : acc}, 0);
}

const min = 1;
const max = 10;
const excludeArray = [8,2,5];
const result = getRandomWithExclude(min, max, excludeArray);

Hmz :-? Fastest way to randomly get items from an array and ensure they're all unique would be:

var array = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24];

Array.prototype.shuffle = function shuffle(){
    var tempSlot;
    var randomNumber;
    for(var i =0; i != this.length; i++){
        randomNumber = Math.floor(Math.random() * this.length);
        tempSlot = this[i]; 
        this[i] = this[randomNumber]; 
        this[randomNumber] = tempSlot;
    }
}

while(array.length!=0){
    array.shuffle();
    alert(array.pop());    
}

Just found myself in a situation where I needed to generate a random number in a really long range, for each game coordinate, BUT excluding some coordinates that are already taken.

As you can imagine recalculation happens between frames (within 10-14ms ideally), so using recursion, while-loop or generating extremely long array are not even an options.

Thanks Salman A and Sebastian Umiński for showing another more performant way of solving the problem.

So here's my revised ES6 function and I hope it helps somebody in a situation that I found myself in :)

const randNum = (min, max, exclude = []) => {
  let num = Math.floor(Math.random() * (max - min + 1 - exclude.length) + min);
  exclude
    .slice()
    .sort((a, b) => a - b)
    .every((exeption) => exeption <= num && (num++, true));
  return num;
};

console.log(randNum(0, 24, [8]));

I'm sure there are a few ways to do this, but you could put all the numbers into something like a stack, jumble it all up and then pop off of it to get your random numbers. Or, randomly seek into it every time and remove it from the stack.

step 1> create an array CHECK_ARRAY fill the array with value which is out of the range of your random number [fill it with 26 if you want to generate number within 0-25]

step2-> generate a random number and add it to RANDOM_ARRAY and also add it to the CHECK_ARRAY that is

i=0;
CHECK_ARRAY[i]=random;
i++;

step3-> generate a new random number and go though the CHECK_ARRAY, if you found 26 then ignore, else if you found duplicate then re-generate a random number and continue step 3 again until you found an unique random number !

Here is a tested and simple solution:

var array= [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24];
var random_value; 
var index;
var shuffled_array = new Array(24);

for (var i = 0; i < 24; i++) { 
random_value = array[Math.floor(Math.random()*array.length)]; //Returns a value between 1 and 24
index = array.indexOf(random_card); //Gets the index of the choosen random value
array.splice(index, 1); //Go to index of that array and remove it
shuffled_array [i] = random_value; //Put that value in a new array

window.alert("array: "+array+"\n"+"random_value: "+random_value+"\n"+"shuffled_array: "+shuffled_array);
}

In other solutions i believe they forgot to search for the index.

Adding up on the great answer by @Alex Chebotarsky.

After some unit testing I found that some additional checks are prudent:

/**
 * Generates a random int within the max and min range.
 * Maximum is exclusive and minimum is inclusive.
 * @param min
 * @param max
 */
export const randomInt = (
  min: number,
  max: number,
): number => (Math.floor(Math.random() * (Math.floor(max) - Math.ceil(min)) + Math.ceil(min)));

/**
 * Generates a random int within the max and min range with an array of excludes.
 * Maximum is exclusive and minimum is inclusive.
 * @param min
 * @param max
 * @param excludes
 */
export const randomIntWithExclude = (
  min: number,
  max: number,
  excludes: number[] = [],
): number => {
  if (min === max && excludes.includes(min)) throw new RangeError('All values are excluded');
  if (min === max) return min;
  if (max < min) [max, min] = [min, max];

  let num = randomInt(min, max);
  if (!excludes || !excludes.length) return num;

  excludes
    .sort((a, b) => a - b)
    .every((except) => except <= num && (num >= max ? num -= 1 : num += 1, true));
  if (excludes.includes(num)) throw new RangeError('All values are excluded');
  return num;
};

If you are interested, here goes the unit test:

import {
  genRndNumUniqArray,
  randomIntWithExclude,
  randomInt,
} from './mathFuncs';

describe('[NumberFuncs]', () => {
  test.repeats(
    { times: 1000 },
    '[randomIntWithExclude] Should generate a random number excluding values in an array',
    () => {
      const excludesLength = randomInt(0, 10);
      const excludes = excludesLength
        ? genRndNumUniqArray(0, 100, excludesLength)
        : [];

      const [min, max] = excludes.length
        ? [Math.min(...excludes), Math.max(...excludes)]
        : [randomInt(0, 10), randomInt(10, 100)];

      try {
        const num = randomIntWithExclude(min, max, excludes);
        expect(num).not.toBeIncludedIn(excludes);
        expect(num).toBeGreaterThanOrEqual(min);
        expect(num).toBeLessThan(max);
      } catch (error) {
        if (min === max && excludes.includes(min)) {
          expect(error).toBeInstanceOf(RangeError);
        }
      }
    },
  );

  test.repeats(
    { times: 100 },
    '[randomIntWithExclude] Should throw a `RangeError` if all possible values are in the excludes array',
    () => {
      const excludes = [...Array(randomInt(2, 10)).keys()];
      const [min, max] = [Math.min(...excludes), Math.max(...excludes)];

      try {
        randomIntWithExclude(min, max, excludes);
        expect(true).toBe(false); // This is not supposed to be reached since the code above throws an error
      } catch (error) {
        if (min === max && excludes.includes(min)) {
          expect(error).toBeInstanceOf(RangeError);
        }
      }
    },
  );
});

This function is a dependency for the unit test:

/**
 * Generates an array of unique numbers
 * @param min
 * @param max
 * @param size
 */
export function genRndNumUniqArray(min: number, max: number, size: number): number[] {
  const rng = Math.min(max - min, size);
  if (rng < 1) return [];
  const nums = new Set<number>();
  while (nums.size !== rng) {
    const n = randomInt(min, max);
    nums.add(n);
  }
  return Array.from(nums);
}

And if you are even more interested about the test.repeats, it is a custom jest extension:

./jest.extends.ts

const handleError = ({
  name,
  errors,
  failPct,
  canFailPct,
  passIfOnePasses,
  debug,
  times,
  passes,
}: {
  name: string,
  times: number,
  canFailPct: number,
  passIfOnePasses?: boolean,
  passes: number[]
  errors: [number, any][],
  failPct: number,
  debug?: boolean,
}) => {
  if (passIfOnePasses && passes.length) return;

  if (errors.length && failPct > (canFailPct ?? 0)) {
    if (debug) {
      throw new Error(`
Test: ${name}
Ran: ${times} times
Failures: \x1b[31m${errors.length}\x1b[0m
Passes: \x1b[32m${passes.length}\x1b[0m
Fail rate: \x1b[31m${failPct * 100}%\x1b[0m
${canFailPct ? `Failed more than the ${canFailPct * 100}% limit` : ''}\n
Errors:
${errors.map((e) => `RUN: ${e[0]}\n${e[1].message}`).join('\n\n')}
`);
    } else {
      throw new Error(`
Test: ${name}
Ran: ${times} times
Failures: \x1b[31m${errors.length}\x1b[0m
Passes: \x1b[32m${passes.length}\x1b[0m
Fail rate: \x1b[31m${failPct * 100}%\x1b[0m
${canFailPct ? `Failed more than the ${canFailPct * 100}% limit` : ''}\n
Last error:
${errors[errors.length - 1][1]}\n
You can pass the \x1b[1;33m\`debug: true\`\x1b[0m option to see all errors.
`);
    }
  }
};

const repeatTest = async (
  options: jest.RepeatWithCanFail | jest.RepeatWithPass | jest.RepeatWithDefaults,
  name: string,
  fn?: jest.ProvidesCallback,
  timeout?: number,
) => {
  if (options.canFailPct && (options.canFailPct < 0 || options.canFailPct > 1)) {
    throw new Error('`canFailPct` must be between 0 and 1');
  }

  const passes: number[] = [];
  const errors: [number, any][] = [];

  return test(name, async () => {
    for await (const i of [...Array(options.times).keys()]) {
      try {
        if (fn) {
          // @ts-ignore
          await fn();
          passes.push(i);
        }
      } catch (error) {
        errors.push([i, error.stack ?? error.toString()]);
      }
    }
    const failPct = errors.length / options.times;

    handleError({
      name,
      errors,
      failPct,
      canFailPct: options.canFailPct ?? 0,
      passIfOnePasses: options.passIfOnePasses,
      debug: options.debug,
      times: options.times,
      passes,
    });
  }, timeout);
};

test.repeats = repeatTest;
it.repeats = repeatTest;

It prints this on failing tests:

  [NumberFuncs]
    ✕ [getRandomIntWithExclude] (216 ms)

  ● [NumberFuncs] › [randomIntWithExclude]


    Test: [randomIntWithExclude]
    Ran: 1000 times
    Failures: 95
    Passes: 905
    Fail rate: 9.5%


    Last error:
    Error: expect(received).toBeGreaterThanOrEqual(expected)

    Expected: >= 67
    Received:    66

./jest.config.js

Make sure to run the extension file before tests and include the jest custom types in jest.d.ts and tsconfig.json if using typescript.

/** @type {import('ts-jest/dist/types').InitialOptionsTsJest} */
module.exports = {
  ...
  setupFilesAfterEnv: ['./jest/extends.ts'],
  ...
};

jest.d.ts

export {}
declare global {
  namespace jest {  
    type RepeatWithCanFail = {
      times: number,
      canFailPct: number,
      passIfOnePasses?: undefined,
      debug?: boolean,
    }
    
    type RepeatWithPass = {
      times: number,
      canFailPct?: undefined,
      passIfOnePasses: boolean,
      debug?: boolean,
    }
    
    type RepeatWithDefaults = {
      times: number,
      canFailPct?: undefined,
      passIfOnePasses?: undefined,
      debug?: boolean,
    }

    type RepeatOpts<O = any> =
    O extends RepeatWithCanFail
    ? RepeatWithCanFail
    : O extends RepeatWithPass
    ? RepeatWithPass
    : RepeatWithDefaults;

    interface It {
      repeats: <O extends RepeatOpts>(
        options: RepeatOpts<O>,
        name: string,
        fn?: jest.ProvidesCallback,
        timeout?: number,
      ) => void;
    }
  }
}

<div id="number" style="color: red; margin-left: 200px;">array</div>
<div id="arr" style="color: red; margin-left: 200px;">length</div>
<script>
  var arrayOfIndexesToExclude = new Array();
  function getRandomWithManyExclusions(){
    var rand = null;
      
		  	do{
		    	rand = Math.round(Math.random() * ( 9));
		    	if(arrayOfIndexesToExclude.length >= 10){
		 			  arrayOfIndexesToExclude.length = 0;	   			
		    	}
				}while(arrayOfIndexesToExclude.includes(rand));
			
			arrayOfIndexesToExclude.push(rand);  
    
    document.getElementById("number").innerHTML = arrayOfIndexesToExclude;
    document.getElementById("arr").innerHTML = arrayOfIndexesToExclude.length;
  }
</script>