Do not select object from array again for x selections in JS

Question

I have an array of objects of countries

const countries = [
  {
    capital: "Kabul",
    countryISOCode: "af",
    continent: "Asia",
    countryFullName: "Afghanistan",
  },
  {
    capital: "Mariehamn",
    countryISOCode: "ax",
    continent: "Europe",
    countryFullName: "Aland Islands",
  },
  {
    capital: "Tirana",
    countryISOCode: "al",
    continent: "Europe",
    countryFullName: "Albania",
  },
  {
    capital: "Algiers",
    countryISOCode: "dz",
    continent: "Africa",
    countryFullName: "Algeria",
  },
  {
    capital: "Pago Pago",
    countryISOCode: "as",
    continent: "Oceania",
    countryFullName: "American Samoa",
  },
  {
    capital: "Andorra la Vella",
    countryISOCode: "ad",
    continent: "Europe",
    countryFullName: "Andorra",
  }
]

I want to randomly select an object which I currently do with
const randomCountry = Math.floor(Math.random() * countries.length);

Problem is that there are often duplicates, i.e. the same country gets chosen twice in a row. I want to add that a country is not able to be selected again for x amount of random selections to make sure it does not appear so often. What would be the best approach to make this work?

Randomly sort the array and then just iterate over it instead of selecting a random element each time? — David, Aug 17 '23 at 18:36
I worded this wrongly, there are no duplicates in the array itself, but the randomly selected country is often the same as a previously chosen one before. I cannot change the size of the country-list as well — David Moll, Aug 17 '23 at 18:40
So do what David said: Shuffle the array and then select items in order. — Barmar, Aug 17 '23 at 18:43
Does this answer your question? [How to randomize (shuffle) a JavaScript array?](https://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array) — imvain2, Aug 17 '23 at 18:46
Like previously mentioned, if you shuffle the array the contents will be in a random order. Then you can just cycle from the first to the last knowing that you won't get a duplicate. — imvain2, Aug 17 '23 at 18:47
@imvain2 If I didn't understand wrong, OP asks the countries not get randomly selected more than few times. They will still be selected randomly but a limitation is needed. — M. Çağlar TUFAN, Aug 17 '23 at 18:55

M. Çağlar TUFAN · Answer 1 · 2023-08-17T18:49:22.213

An obvious solution at first thought comes to my mind is adding another property to data structure of countries which will store the data of count of selection.

We can call this property timesSelected. Whenever an object gets randomly selected we will increment this property by 1. If you don't want a country to be selected more than, lets say twice, we can confitionally check if timesSelected property's value is less than 2.

const countries = [
  {
    capital: "Kabul",
    countryISOCode: "af",
    continent: "Asia",
    countryFullName: "Afghanistan",
    timesSelected: 0
  },
  {
    capital: "Mariehamn",
    countryISOCode: "ax",
    continent: "Europe",
    countryFullName: "Aland Islands",
    timesSelected: 0
  },
  {
    capital: "Tirana",
    countryISOCode: "al",
    continent: "Europe",
    countryFullName: "Albania",
    timesSelected: 0
  },
  {
    capital: "Algiers",
    countryISOCode: "dz",
    continent: "Africa",
    countryFullName: "Algeria",
    timesSelected: 0
  },
  {
    capital: "Pago Pago",
    countryISOCode: "as",
    continent: "Oceania",
    countryFullName: "American Samoa",
    timesSelected: 0
  },
  {
    capital: "Andorra la Vella",
    countryISOCode: "ad",
    continent: "Europe",
    countryFullName: "Andorra",
    timesSelected: 0
  }
]

const randomlySelectACountry = () => {
  const randomCountryIndex = Math.floor(Math.random() * countries.length);
  const countrySelected = countries[randomCountryIndex];

  // Check if the timesSelected proeprty's value is greater than or equal to 2
  if(countrySelected.timesSelected >= 2) {
    return randomlySelectACountry();
  }
  
  // Increment timesSelected proeprty of selected country by 1
  countrySelected.timesSelected++;

  return countrySelected;
};

Important note: In this code randomlySelectACountry function calls itself if the randomly selected country's timesSelected property's value is greater than or equal to 2. This selection code is not optiomal since it can still randomly select countries with timesSelected property's value greater than or equal to 2. To optimize and prevent this behaviour, we can either filter the countries array to match only country which have timesSelected property's value is less than 2 or we can filter out whenever a selected country's timesSelected proeprty's value becomes greater than 2. First approach gives you possibility to have countries array untouched (except of timesSelected property of course) and second approach reduces the countries array each time a country has been selected at least 2 times.

It has the same problem as the answer suggested using `Set`. It's better to just shuffle the array. — Kosh, Aug 17 '23 at 18:56
@Kosh no I doesn't. Set allows a member to be added only once, it ensures that. But using this approach you can limit a selection of countries more than once. You are mistaken the problem here. — M. Çağlar TUFAN, Aug 17 '23 at 19:00
@Kosh and not to mention that when you shuffle the array and then reach to the last element as selected country, you will need to re-shuffle the array and select the first element as randomly selected element. Chances are the 2nd shuffle's first element can be same as 1st shuffle's last element. — M. Çağlar TUFAN, Aug 17 '23 at 19:03
@Kosh you might say you don't need to re-shuffle but then there will occur a pattern which is antiparallel to randomisation. — M. Çağlar TUFAN, Aug 17 '23 at 19:05
OK. To your code: let's say on the first run we randomly get `randomCountryIndex = 1`, we show country#1; then on the second run we randomly get `randomCountryIndex = 1` again; we show country#1 again. Result is the same country twice in a row. Another problem -- when each country was displayed twice, your code goes to infinite recursion. — Kosh, Aug 17 '23 at 19:29
@Kosh you probably didn't read the note below the code I provided. — M. Çağlar TUFAN, Aug 17 '23 at 20:16

Mr. Polywhirl · Answer 2 · 2023-08-17T20:41:52.837

In the snippet below, the arrayRandomizer is an object with a get() method which will always produce a random number from the input array. The chance of a duplicate decreases as the cacheSize is increased. Each item is selected exactly one time, before re-indexing occurs. The cache remembers the previously selected items.

In the example below, the cacheSize is set to 2. This means that a duplicate will not appear until a third selection is made.

Note: I kept log statements, if you would like to debug the state of the randomizer each time you request another value.

const main = () => {
  //console.log('START');
  let prev;
  const randomizer = arrayRandomizer(countries, 2);
  for (let i = 0; i < 100; i++) {
    const [index, country] = randomizer.get();
    if (country === prev) {
      //console.error('PREV!');
    }
    console.log(index, format(country));
    prev = country;
  }
  //console.log('DONE');
};

const randSort = () => 0.5 - Math.random();

const arrayRandomizer = function(arr, cacheSize = 1) {
  const randomize = () =>
    Array.from(arr, (_, i) => i).sort(randSort);
    
  let randomIndices = randomize();
  let cache = new Set();

  return ({
    get() {
      const [currIndex] = randomIndices.splice(0, 1);
      const next = arr[currIndex];
      const delta = arr.length - (arr.length - randomIndices.length);
      if (delta < cacheSize) {
        //console.error('ADDING TO CACHE:', currIndex, 'DELTA:', delta);
        cache.add(currIndex);
      }
      if (randomIndices.length === 0) {
        const newIndices = randomize();
        randomIndices = [
          ...newIndices.filter(n => !cache.has(n)), // Non-cached, up front
          ...newIndices.filter(n => cache.has(n)),  // Cached, at the end
        ];
        //console.error('PREV CACHE:', ...[...cache], 'NEW INDICES:', ...randomIndices);
        cache.clear();
      }
      return [currIndex, next];
    }
  })
};

const format = ({ capital, countryFullName }) =>
  `${capital}, ${countryFullName}`;

const countries = [{
  capital: "Kabul",
  countryISOCode: "af",
  continent: "Asia",
  countryFullName: "Afghanistan",
}, {
  capital: "Mariehamn",
  countryISOCode: "ax",
  continent: "Europe",
  countryFullName: "Aland Islands",
}, {
  capital: "Tirana",
  countryISOCode: "al",
  continent: "Europe",
  countryFullName: "Albania",
}, {
  capital: "Algiers",
  countryISOCode: "dz",
  continent: "Africa",
  countryFullName: "Algeria",
}, {
  capital: "Pago Pago",
  countryISOCode: "as",
  continent: "Oceania",
  countryFullName: "American Samoa",
}, {
  capital: "Andorra la Vella",
  countryISOCode: "ad",
  continent: "Europe",
  countryFullName: "Andorra",
}];

main();

.as-console-wrapper { top: 0; max-height: 100% !important; }

Alexander Nenashev · Answer 3 · 2023-08-17T20:47:42.713

Use a stack and pool scenario. Select randomly from the pool and keep the temporarily locked countries in the stack.

Note that stack here is not a data structure, just a storage name I like, it's really a queue.

const pool = countries.slice(), stack = [], STACK_SIZE = 4;

let count = 30;
while(count--){
  const idx = Math.random() * pool.length | 0; // get a random index in the pool
  console.log(pool[idx].countryFullName); // get the random counry from the pool and do something
  stack.push(...pool.splice(idx, 1)); // push from the pool into the stack
  stack.length > STACK_SIZE && pool.push(stack.shift()); // move the oldest stack country if full back into the pool
}

<script>
const countries = [
  {
    capital: "Kabul",
    countryISOCode: "af",
    continent: "Asia",
    countryFullName: "Afghanistan",
    timesSelected: 0
  },
  {
    capital: "Mariehamn",
    countryISOCode: "ax",
    continent: "Europe",
    countryFullName: "Aland Islands",
    timesSelected: 0
  },
  {
    capital: "Tirana",
    countryISOCode: "al",
    continent: "Europe",
    countryFullName: "Albania",
    timesSelected: 0
  },
  {
    capital: "Algiers",
    countryISOCode: "dz",
    continent: "Africa",
    countryFullName: "Algeria",
    timesSelected: 0
  },
  {
    capital: "Pago Pago",
    countryISOCode: "as",
    continent: "Oceania",
    countryFullName: "American Samoa",
    timesSelected: 0
  },
  {
    capital: "Andorra la Vella",
    countryISOCode: "ad",
    continent: "Europe",
    countryFullName: "Andorra",
    timesSelected: 0
  }
]
</script>

score -1 · Answer 4 · answered Aug 17 '23 at 18:39

If you are looking for a list of random countries then you can consider using a Set

If not you can add the country to a set you store in a variable and then when selecting a new country check if it exists in the set and if it does select a new one.

From the MDN page:

const mySet1 = new Set();

mySet1.add(1); // Set(1) { 1 }
mySet1.add(5); // Set(2) { 1, 5 }
mySet1.add(5); // Set(2) { 1, 5 }
mySet1.add("some text"); // Set(3) { 1, 5, 'some text' }

mySet1.has(1); // true
mySet1.has(3); // false, since 3 has not been added to the set
mySet1.has(5); // true

This is an inefficient way to do it when the set gets large, since the selection will be found most of the time. It's better to just shuffle the array. — Barmar, Aug 17 '23 at 18:41

Do not select object from array again for x selections in JS

4 Answers4