Typescript 如何调整项目数组，但允许权重影响顺序

我假设数组中的对象将有一个数字weight属性，可以用来确定权重，还有一个value属性，用来保存您关心的数据.因此，该数组的类型为Array<{value: unknown, weight: number}>.我还将使用Math.random()生成一个在0(含)和1(不含)之间统一 Select 的随机数.如果您有不同格式的对象，或者具有接受种子的自定义随机数生成器，您可以调整下面的答案以适应这一情况.我在这里认为这些都超出了范围，特别是因为您的random(seed)函数不能供其他人使用，并且没有足够的规范来回答使用它的问题(例如，它在0和1之间是否像Math.random()一样统一？如果你用相同的种子拨打random()两次，你会得到两个不同的答案吗？或者种子也需要进化吗？等).

还请注意，下面的实现不一定具有最佳的时间复杂性.它是O(n²)，因为weightedIndexChoice()是O(N)，weightedShuffle()调用它n次.如果最优时间复杂性很重要，显然还有其他解决方案可以在O(Nlogn)中做到这一点，这是更好的.下面的另一个答案显示了如何用Python实现它，大概有人可以想出一个JS/TS实现并将其发布在这里.

Fisher-Yates shuffle基本上只是通过随机从第一个数组中挑选(和移除)元素，并将它们推到新的数组中来构建一个新的array.有多种方法可以实现这一点.下面的方法是从数组的开始位置遍历到数组的末尾，并将一个随机元素从数组后面的位置交换到当前位置:

function weightedShuffle(arr: { value: unknown, weight: number }[]) {
    for (let i = 0; i < arr.length; i++) {
        const v = weightedIndexChoice(arr.slice(i));
        [arr[i + v], arr[i]] = [arr[i], arr[i + v]];
    }
}

上面问题的重要部分是weightedIndexChoice()，它需要随机 Select 一个数组的索引，按weight加权.请注意，由于您希望更多权重较大的元素更有可能出现在数组的第start位，这意味着我们需要将第一个随机 Select 的元素放在数组的开头.Fisher-Yates的一些实现从数组的末尾开始执行，对于统一随机 Select ，这并不重要.但如果我们在不改变权重的情况下这样做，最终会在末尾放置更多权重较大的元素，这不是您想要的.

肯定存在涉及如何实现weightedIndexChoice()的堆栈溢出问题/答案.例如，How to choose a weighted random array element in Javascript?.这里有一种方法:

function weightedIndexChoice(arr: { value: unknown, weight: number }[]): number {
    const totalWeight = arr.map(v => v.weight).reduce((x, y) => x + y);
    const val = Math.random() * totalWeight;
    for (let i = 0, cur = 0; ; i++) {
        cur += arr[i].weight;
        if (val <= cur) return i;
    }
}

从本质上讲，您可以 Select 一个介于0和权重总和之间的随机数.然后，通过计算元素权重的累积和，直到传递随机数，从而计算出哪个元素索引对应于该数字.作为一个简单的例子，让我们假设您有三个元素:[{value: "a", weight: 1}, {value: "b", weight: 2}, {value: "c", weight: 3}].总重量是6磅.因此，您可以在0(含)和6(不含)之间随机 Select 一个数字."a"个权重的累积和为1；"b"个权重的累积和为1+2=3；"c"个权重的累积和为1+2+3=6.所以如果你的随机数在0到1之间，你会 Select "a"，如果在1到3之间，你会 Select "b"，如果在3到6之间，你会 Select "c".你可以看到， Select 每个元素的机会与其权重成正比.

我不确定测试这一点的最好方法，但从您的示例开始

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

我们可以构建上面接受的表单的数组:

const arr = items.map((value, i) => ({ value, weight: weights[i] }));

多次运行洗牌，并跟踪结果:

const results: number[][] = [];
const numTrials = 100_000;
for (let i = 0; i < numTrials; i++) {
    weightedShuffle(arr);
    results.push(arr.slice().map(v => v.value))
}

然后...嗯，最容易判断的是每个结果数组第一个元素的相对权重，因为这应该与您的权重成正比:

const firstPos: Record<number, number> = {};
items.forEach(v => firstPos[v] = 0);
results.forEach(vals => firstPos[vals[0]] = (firstPos[vals[0]] ?? 0) + 1);
const totalWeight = weights.reduce((x, y) => x + y);

// this is the weighted occurrence of the first element of the shuffled array
console.log(Object.entries(firstPos).map(([k, v]) => [k, v * totalWeight / numTrials]));
// [["1", 0.93834], ["2", 0.98646], ["3", 1.02255], ["4", 199.20477], ["5", 1000.84788]] 

实际记录的结果将取决于 Select 的随机数，但这是有希望的.

在此之后，您could开始判断每个结果的第二个元素，条件是第一个元素不可用，并显示结果与预期一致.但坦率地说，我们所做的只是对费舍尔-耶茨洗牌进行反向工程，并确保加权指数的 Select 符合我们的预期.不确定这是否值得go 做.

Playground link to code个