0

I have an array containing some items, let's say numbers:

[23,4,67,8,29,46,7,2,98]

How it is possibile to choose N different random number (no more, no less) from the array?

Behaviour expected: if N=3

[4,23,98] accepted
[7,67,29] accepted
[7,67,7]  not accepted

EDIT: Finally I've found a pretty good solution. The thread as been closed so I'm publishing my solution here just for people passing by. I had an array long M and N numbers to choose so I made an array containing M numbers (indexesArray) applied the Fisher Yates algorithm to shuffle number corresponding this way to indexes of my initial array and took the first M items from that. Thanks to @ArneHugo for pointing the right path to follow.

var arrayContainingNumbersToChoose=[23,4,67,8,29,46,7,2,98];
var indexesArray=[];
var N=5;
var resultArray=[];

var M=arrayContainingNumbersToChoose.length;

for (let i = 0; i < M; i++) {
   indexesArray.push(i);
} // result like [0, 1, 2, 3, 4, 5, 6, 7, 8]

indexesArray=fisherYatesShuffle(indexesArray); // result like [2, 4, 7, 6, 0, 1, 3, 8, 5]

for (let i = 0; i < N; i++) {
resultArray.push(arrayContainingNumbersToChoose[indexesArray[i]]);
}

console.log(resultArray);

function fisherYatesShuffle(a) {
      var j, x, i;
      for (i = a.length - 1; i > 0; i--) {
          j = Math.floor(Math.random() * (i + 1));
          x = a[i];
          a[i] = a[j];
          a[j] = x;
      }
      return a;
  }
Sasha Grievus
  • 2,566
  • 5
  • 31
  • 58
  • 1
    Is performance important? Can you mutate the array? – ArneHugo Jun 11 '18 at 14:47
  • Performance is important, i can mutate the array – Sasha Grievus Jun 11 '18 at 14:47
  • this looks a bit like a "do my homework"-question. Also, could you let us know if you tried anything? – Burki Jun 11 '18 at 14:49
  • 1
    Hi! This issue has been [repeatedly asked and answered](/search?q=%5Bjs%5D+random+array+without+repeat). Please search before posting. More about searching [here](/help/searching). – T.J. Crowder Jun 11 '18 at 14:50
  • Sorry, I swear I tried searching but each answer had different problems. I tried choosing indexes of the array as random number excluding already chosen but this could be bad performant, taking a lot more step this issue could require. – Sasha Grievus Jun 11 '18 at 14:59
  • 1
    @SashaGrievus Mods on SO are very aggressively blocking a thread by marking them as duplicates. Sometimes this happens so fast that I doubt they could have read the original well, or the duplicate answer. While I understand the need to avoid duplicates, this marking happens too fast. – Erwin Moller Jun 11 '18 at 15:06
  • @ArneHugo By mutate you are implying I could shuffle the array and taking the first N element maybe? This could be a good performant way to approach the problem – Sasha Grievus Jun 11 '18 at 15:09

1 Answers1

0

Try the following:

var arr = [23,4,67,8,29,46,7,2,98];
var result = [];
var map = {};
var n = 3;
var i = arr.length;
var counter = arr.length+n;
while(result.length != n){
      num = arr[Math.floor(Math.random() * i)];
      if(!map[num]){
        map[num] = i;
        result.push(num);
      }
      if(counter <= 0) // stop finding random numbers if counter is zero.
        break;
      counter--;
      i--;
      if(i  == 0)
        i = arr.length;
}
console.log(result);
amrender singh
  • 7,949
  • 3
  • 22
  • 28
  • cool, but that while couldn't go on forever if you're very very very unlucky? Performance was a problem I was trying to deal with – Sasha Grievus Jun 11 '18 at 14:56
  • @SashaGrievus i have updated the answer, i have limited the while loop. it will not run infinitely now. – amrender singh Jun 11 '18 at 14:59
  • thank you very much. But let's say that at some point num keeps being only numbers already chosen, this could go forever anyway, couldn't? I understand that this case is at limit and absurd, but still means that if a big number of 'already chosen num' is generated, this could require a lot more step than required causing bad performance, i guess – Sasha Grievus Jun 11 '18 at 15:05
  • @SashaGrievus The while loop wont go forever as we decrement counter in each iteration. So when the counter becomes zero, we break the loop. – amrender singh Jun 11 '18 at 15:07
  • Umh, this is being executed max 'counter' times that in this case is array.lenght+n=9+3=12. Having 12 possibilities to generate the number, if random numbers are to be discarded 10 times this couldn't result in having only 2 items in variable 'result'? Unlikely, but could? – Sasha Grievus Jun 11 '18 at 15:16
  • 1
    @SashaGrievus yes correct, to prevent that you can splice that element from array, only when the element is repeated. – amrender singh Jun 11 '18 at 15:18