samedi 21 octobre 2023

How to shuffle array of items but allow weights to influence the order

I'm trying to write a TypeScript function to shuffle an array.

By default, I want the shuffle order to be random (but subject to a seed). (I already have access to this function: function random(seed: number): number)

However, I want to also allow influencing the order via weights per item.

In other words, I want the the default item weight to be 1, and if an item has a weight of 10, it should be 10 times more likely to appear sooner in the shuffled order.

Am I even thinking about this correctly? Is this a reasonable goal?

I was thinking that I'd need to use the Fisher-Yates algorithm but adapted to honor a weights array of the same length as the main array, and the main array will be shuffled such that higher weighted items are more likely to appear first.

function removeDuplicates<T>(array: T[]): T[] {
  const uniqueValues = new Set<T>();
  return array.filter((item) => {
    if (!uniqueValues.has(item)) {
      uniqueValues.add(item);
      return true;
    }

    return false;
  });
}

function duplicateItemsBasedOnWeights<T>(array: T[], weights: number[]): T[] {
  const result = [];
  for (const [index, element] of array.entries()) {
    for (let position = 0; position < weights[index]; position++) {
      result.push(element);
    }
  }

  return result;
}

export function shuffleWithWeights<T>(array: T[], weights: number[], seed: number): T[] {
  const arrayWithDuplicateValuesBasedOnWeights: T[] = duplicateItemsBasedOnWeights(array, weights);

  const shuffledArrayWithDuplicateValuesBasedOnWeights = shuffleArrayUsingFisherYates(arrayWithDuplicateValuesBasedOnWeights, seed);

  return removeDuplicates(shuffledArrayWithDuplicateValuesBasedOnWeights);
}

I've looked at empirical results by calling it a bunch of different times with these values (and a different seed each time), and the results don't seem distributed how I'd hoped, so I must have been approaching this problem incorrectly.

const items = [1, 2, 3, 4, 5];
const weights = [1, 1, 1, 200, 1_000];

In my real-world cases, I'll be shuffling 70,000 objects (which would explore to many more than that if I use my current approach of creating duplicate items based on item weight).




Aucun commentaire:

Enregistrer un commentaire