Set key of random objects to a different value

Question

I'm given an input = 5.

I want to set the is_winner key to true of 5 random objects in this array.

const participants = [
    {code: '111111', is_winner: false},
    {code: '222222', is_winner: false},
    {code: '444444', is_winner: false},
    {code: '777777', is_winner: false},
    {code: '555555', is_winner: false},
    {code: '666666', is_winner: false},
    {code: '333333', is_winner: false},
    {code: '888888', is_winner: false},
    {code: '999999', is_winner: false},
];

First randomization:

const participants = [
    {code: '111111', is_winner: false},
    {code: '222222', is_winner: true},
    {code: '444444', is_winner: false},
    {code: '777777', is_winner: true},
    {code: '555555', is_winner: false},
    {code: '666666', is_winner: true},
    {code: '333333', is_winner: true},
    {code: '888888', is_winner: false},
    {code: '999999', is_winner: true},
];

I tried the following which has 2 for loops, and one of them is an O(n^2)

const winners = [];

while (winners.length < 5) {
    const randomParticipant = participants[Math.floor(Math.random() * participants.length)];

    if (!winners.includes(randomParticipant.code)) {
        winners.push(randomParticipant.code);
    }
}

for (let participant of participants) {
    if (winners.includes(participant.code)) {
        participant.is_winner = true;
    }
}

Looking to see if there is something more efficient.

Looks like homework. He posted a similar question not too long ago. SOF is not a homework solution tool — mwilson, Jun 19 '19 at 22:36
@mwilson I have my solution posted in the question. I'm trying to get better to see what's out there. Thank you for your comprehension. — Anthony, Jun 19 '19 at 22:38
Make an array of numbers from `0` to `participants.length-1`. Shuffle the array, take the first 5 elements, and use those as indexes to change `is_winner`. — Barmar, Jun 19 '19 at 22:45
`winners.includes()` is O(n), so your whole algorithm is O(n^2). Use a `Set` instead of an array to solve this. — Barmar, Jun 19 '19 at 22:46

Akrion · Accepted Answer · 2019-06-20T05:43:29.617

You can also consider doing this with Set and Array.forEach like this:

const participants = [ {code: '111111', is_winner: false}, {code: '222222', is_winner: false}, {code: '444444', is_winner: false}, {code: '777777', is_winner: false}, {code: '555555', is_winner: false}, {code: '666666', is_winner: false}, {code: '333333', is_winner: false}, {code: '888888', is_winner: false}, {code: '999999', is_winner: false}, ];

let randomize = (arr, n=5, clone=true) => {
  let set = new Set(), _arr = arr
  if(clone) _arr = arr.map(x => ({...x})) // skip if you want to mutate
  while(set.size < n) set.add(Math.floor(Math.random() * participants.length))
  Array.from(set).forEach(x => _arr[x].is_winner = true)
  return _arr
}

console.log(randomize(participants))
console.log(randomize(participants, 3))

The Set and the while takes care of generating an array of the random numbers (in your case array indexes). Once you have that then you simply set the is_winner to true via the Array.forEach.

Since it is preferable for the functions to not mutate the input I added the clone flag but if you do not care about that you can remove it and also the if(clone) line which just create a clone of the array.

score 0 · Answer 2 · answered Jun 19 '19 at 23:33

// Found a nice way to shuffle in this SOF post https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array
const shuffle = (array) => {
    for (let i = array.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
    return array
};

// Selects random participants and set their is_winner key to true.
const setRandomWinners = (numberOfWinners) => {
    const arr = [...Array(participants.length).keys()];
    const shuffledArr = shuffle(arr);
    const newArr = shuffledArr.slice(0, numberOfWinners);

    for (let el of newArr) {
        participants[el].is_winner = true;
    }
};

Set key of random objects to a different value

2 Answers2