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