How to randomize 2 lists so that items of the same index aren't identical?

user_9882780 0
Viewed 52

Say I have 2 lists with identical items that I've shuffled like below:

listA = [1, 3, 2];
listB = [2, 3, 1];

I want to make sure that list items of the same index don't match. So I wouldn't want listA[1] to match with listB[1]. How do I randomize both lists so that this doesn't occur?

shuffle javascript
2 Answers

There is probably a more elegant way to do this, but the code below should work, even for arrays of different sizes. It first checks whether it's possible to get the uniqueness you're looking for, and if so it goes into a while loop to continuously shuffle the larger of the two arrays (in place) until it finds a solution.

// First, set up utility functions

function shuffleArray(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}

function smallerAndOther(arr1, arr2) {
  const smallerArr = arr1.length < arr2.length ? arr1 : arr2;
  const otherArr = smallerArr === arr1 ? arr2 : arr1;
  return [smallerArr, otherArr];
}

function anyEqualIdx(arr1, arr2) {
  const [smallerArr, otherArr] = smallerAndOther(arr1, arr2);

  for (let i of smallerArr.keys()) {
    if (smallerArr[i] === otherArr[i]) return true;
  }
  return false;
}

function getCount(array, value) {
  return array.filter((v) => (v === value)).length;
}

// Now for the real stuff

function sufficientUnique(arr1, arr2) {
  const [smallerArr, otherArr] = smallerAndOther(arr1, arr2);

  for (let num of new Set([...smallerArr])) {
    if (otherArr.length - getCount(otherArr, num) < getCount(smallerArr, num)) {
      return false;
    }
  }
  return true;
}

function shuffleUniqueIdxs(arr1, arr2) {
  if (!sufficientUnique(arr1, arr2)) {
    console.log("Error: Not enough unique values to meet constraint.");
    return;
  }
  const largerArr = arr1.length > arr2.length ? arr1 : arr2;
  while (anyEqualIdx(arr1, arr2)) {
    shuffleArray(largerArr);
  }
  console.log("Success: ", arr1, arr2);
}

// Testing 

let listA = [1, 3, 2];
let listB = [2, 3, 1];

shuffleUniqueIdxs(listA, listB);

listA = [7, 5, 5, 3, 9, 9, 1];
listB = [3, 5, 5];

shuffleUniqueIdxs(listA, listB);

listA = [1, 1, 1];
listB = [2, 1, 1];

shuffleUniqueIdxs(listA, listB); // shows error message

listA = [1, 1, 1, 1, 1];
listB = [2, 2, 2, 2, 2];

shuffleUniqueIdxs(listA, listB);

listB = [99, 9, 9, 9, 9, 9, 9, 9, 99, 88, 8, 8, 8, 8, 8, 7, 7, 6, 65, 5, 5, 5, 4]
listA = [9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 6];

shuffleUniqueIdxs(listA, listB);

user_11749660

Here's one solution. It first individually shuffles both arrays, then it looks for repeated entries and randomly moves those around. Note that this solution only works for arrays of the same size. It is also intended to be used on arrays where most elements are unique (otherwise, it might get stuck randomly moving things around for a while).

const randIntBetween = (left, right) => left + Math.floor(Math.random() * (right - left));

function shuffle(array) {
  array = [...array];
  for (let i = 0; i < array.length; ++i) {
    const newIndex = randIntBetween(i, array.length);
    [array[i], array[newIndex]] = [array[newIndex], array[i]];
  }
  return array;
}

function randomlyMoveRepeatedEntries(array, comparisonArray) {
  array = [...array];
  const indicesToCheck = new Set(array.map((_, i) => i));
  while (indicesToCheck.size) {
    const { value: index } = indicesToCheck.values().next();
    if (array[index] !== comparisonArray[index]) {
      indicesToCheck.delete(index);
      continue;
    }

    const newIndex = randIntBetween(index, array.length);
    [array[index], array[newIndex]] = [array[newIndex], array[index]];
    indicesToCheck.add(newIndex);
  }
  return array;
}

// ----- Example Usage ----- //

const listA = shuffle([1, 2, 3, 4, 5]);
const listB = randomlyMoveRepeatedEntries(shuffle([1, 2, 3, 4, 5]), listA);

console.log(listA.join(', '));
console.log(listB.join(', '));

user_76962230
Related