javascriptconditional-statementsrandomized-algorithm

How to randomize without replacement with conditions?


I have a number of embedded images, which I randomize 4 times without replacement (once an image is seen, you cannot see it again). I'd like to add a condition, which suggests that a set of additional images cannot be seen (not only the image that was previously selected). These are images that have similar traits to the one selected.

To demonstrate:

Let's say I have the following array of vars: BF1, BA1, BF2, BA2, BF3, BA3

I want to randomly draw 3 vars (images) out of the array without replacement, AND I want vars that have the number 2 (same set) to be removed from the next array as well. So, if the first drawn var is BF2, the next draw will be from the following array:

BF1, BA1, BF3, BA3 (only one of these options can randomly appear)

Now let's say I drew the var BF1, so the next set of possible vars will be:

BF3, BA3.

I hope this makes sense. This is the code I have so far for the drawing without replacement:

function shuffle(array){
  var counter = array.length,
  temp, index;
  while (counter > 0){
  index = Math.floor(Math.random() * counter);
  counter = counter-1;
  temp = array[counter];
  array[counter] = array[index];
  array[index] = temp;
  }
  return array;


var myArray = [BF1,BA1,BF2, BA2, BF3,BA3, BA4, BF4, BA5, BF5, BF6, BA6, BF7, BA7, BA8, BF8, BA9, BF9, BF10, BA10, BA11, BF11, BA12, BF12, BA13, BF13, BA14, BF14, BA15, BF15, BA16, BF16, BA17, BF17, BA18, BF18, BA19, BF19, BA20, BF20, BA21, BF21, BF22, BA23, BF23, BA24, BF24, BA25, BF25, BA26, BF26, BA27, BF27, BA28, BF28, BA29, BF29, BA30, BF30, BA31, BF31, BA32, BF33, BA33, BA34, BF35, BA35, BA36, BF36];
    
shuffle(myArray)


Solution

  • You can definitely implement this in any number of ways, but no matter what you use, you'll need to perform the following 3 steps in some capacity (I split them out into separate methods, but you can combine them as you see fit):

    1. Shuffle the list
    2. Pick an item
    3. Filter out the items matching the pick (in this case, those with the same number)

    You have the shuffle routine covered, so that just leaves the pick and the filter.

    For the pick, I just used Math.random to pull a random member of the list:

    return array[Math.floor(Math.random() * array.length)];
    

    For the filter, I used Array.prototype.filter to pull out the desired items. In this case, with the strings, I parse the number out of the string and then remove any items in the array that have the same number as the last pick:

    return array.filter(el => +el.match(/\d+/).join() != +picked.match(/\d+/).join());
    

    But with actual images, you'll just replace that with however you read the labels of your images.

    Example

    Here's the full working example, with the list of picks first, followed by a sorted array of the picks showing they were all used.

    var imageList = ['BF1', 'BA1', 'BF2', 'BA2', 'BF3', 'BA3', 'BA4', 'BF4', 'BA5', 'BF5', 'BF6', 'BA6', 'BF7', 'BA7', 'BA8', 'BF8', 'BA9', 'BF9', 'BF10', 'BA10', 'BA11', 'BF11', 'BA12', 'BF12', 'BA13', 'BF13', 'BA14', 'BF14', 'BA15', 'BF15', 'BA16', 'BF16', 'BA17', 'BF17', 'BA18', 'BF18', 'BA19', 'BF19', 'BA20', 'BF20', 'BA21', 'BF21', 'BF22', 'BA23', 'BF23', 'BA24', 'BF24', 'BA25', 'BF25', 'BA26', 'BF26', 'BA27', 'BF27', 'BA28', 'BF28', 'BA29', 'BF29', 'BA30', 'BF30', 'BA31', 'BF31', 'BA32', 'BF33', 'BA33', 'BA34', 'BF35', 'BA35', 'BA36', 'BF36'];
    
    var selection = imageList.slice();
    
    var picked = [];
    
    function shuffle(array) {
      var counter = array.length, temp, index;
      while (counter > 0) {
        index = Math.floor(Math.random() * counter);
        counter = counter - 1;
        temp = array[counter];
        array[counter] = array[index];
        array[index] = temp;
      }
      return array;
    }
    
    function pick(array) {
      return array[Math.floor(Math.random() * array.length)];
    }
    
    function filterPicked(picked, array) {
      return array.filter(el => +el.match(/\d+/).join() != +picked.match(/\d+/).join());
    }
    
    while (selection.length) {
      // 1. Shuffle
      shuffle(selection);
      // 2. Pick
      picked.push(pick(selection));
      // 3. Filter
      selection = filterPicked(picked[picked.length-1], selection);
    }
    
    console.log(`Picks: [${picked.join(', ')}]`);
    
    console.log(`Sorted picks: [${picked.sort((a, b) => +a.match(/\d+/).join() - +b.match(/\d+/).join()).join(', ')}]`);

    Step-by-step

    1. Shuffle the selection array (a copy of the full array or all selections)
    2. Pick an item off the selection array, push it onto the array of picks
    3. Filter the selection array to remove items matching the last pick
    4. Repeat 1-3 with each newly filtered array, until no selections remain