主页 / coding / 问题 / 77337410
Accepted
Ryan
Asked: 2023-10-22 03:05:22 +0800 CST

如何打乱项目数组但允许权重影响顺序

  • 772

我正在尝试编写一个 TypeScript 函数来打乱数组。

默认情况下，我希望洗牌顺序是随机的（但受种子影响）。（我已经可以使用这个功能了function random(seed: number): number：）

但是，我还想允许通过每个项目的重量来影响订单。

换句话说，我希望默认项目权重为 1，如果一个项目的权重为 10，那么它在打乱顺序中较早出现的可能性应该增加 10 倍。

我是否正确地思考过这个问题？这是一个合理的目标吗？

我认为我需要使用 Fisher-Yates 算法，但适应于与主数组长度相同的权重数组，并且主数组将被洗牌，以便较高权重的项目更有可能首先出现。

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);
}

我通过使用这些值（每次都有不同的种子）多次调用它来查看经验结果，结果似乎没有按照我希望的方式分布，所以我一定是错误地处理了这个问题。

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

在我的现实案例中，我将打乱 70,000 个对象（如果我使用当前基于项目重量创建重复项目的方法，则探索的对象会多得多）。

arrays

2 个回答

  1. Best Answer

    我假设数组中的对象将具有一个weight可用于确定权重的数字属性，以及一个value用于保存您关心的数据的属性。所以数组的类型是Array<{value: unknown, weight: number}>。我也将用来生成一个在（包含）和（不包含）Math.random()之间统一选择的随机数。如果您有不同格式的对象，或者带有种子的自定义随机数生成器，您可以调整下面的答案以适应这种情况。我认为这些超出了这里的范围，特别是因为您的函数无法供其他人使用，并且没有足够指定答案来使用它（例如，它在和like之间是否统一？如果您调用01random(seed)01Math.random()random()使用相同的种子两次，你会得到两个不同的答案，还是种子也需要进化？ETC）。

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

    Fisher -Yates 洗牌基本上只是通过从第一个数组中随机选取（并删除）元素并将它们推入新数组来构建一个新数组。有多种方法可以实现这一点。下面的代码通过从数组的开头走到结尾并将数组后面的随机元素交换到当前位置来实现：

    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()，它需要随机选择数组的索引，并由 加权weight。请注意，既然您说您希望权重较大的元素更有可能出现在数组的开头，这意味着我们需要将第一个随机选择的元素放在数组的开头。Fisher-Yates 的某些实现从数组末尾开始执行此操作，对于均匀随机选择来说这并不重要。但如果我们在不改变权重的情况下这样做，最终会在最后放置更重的权重元素，这不是您想要的。

    肯定有现有的 Stack Overflow 问题/答案涵盖如何实现weightedIndexChoice(). 例如，如何在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;
    }
}

    0本质上，您在权重和总权重之间均匀地选择一个随机数。然后，通过计算元素权重的累积和，直到传递随机数，找出与该数字相对应的元素索引。作为一个简单的例子，让我们假设您有三个元素：[{value: "a", weight: 1}, {value: "b", weight: 2}, {value: "c", weight: 3}]。总重量为6. 0因此，您在（包含）和（不包含）之间选择一个随机数6。权重的累积和1为"a"；1+2=3为"b"; 和1+2+3=6为"c". 因此，如果您的随机数介于0和1您选择之间"a"，如果它介于1和3您选择之间"b"，并且如果它介于3和6你选择"c"。可以看到，每个元素被选择的机会与其权重成正比。

    我不确定测试这个的最佳方法，但从你的例子开始

    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] }));

    运行 shuffle 多次并跟踪结果：

    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]]

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

    之后，您可以开始检查每个结果的第二个元素（条件是第一个元素不可用），并显示结果符合预期。但坦率地说，我们所做的只是对 Fisher-Yates 洗牌进行逆向工程，并确保加权指数的选择符合我们的预期。不确定这是否值得做。

    Playground 代码链接

    • 2

  2. 加权随机抽样，Efraimidis，Spirakis 2005

    论文链接：https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf

    更新

    没有 Javascript 技能，但上面的论文提供了此类洗牌的最佳算法。接受的答案是 O(n 2 )，这将显示在大数据上。

    Efraimidis&Spirakis 是 O(n log(n))，基本上是排序复杂度。

    人们，阅读论文，不要发明轮子。

    WRS 算法、Python 3.10、Windows x64

    import numpy as np

items = np.array([1, 2, 3, 4, 5])
freqs = np.array([1., 1., 1., 200., 1000.0])

wghts = freqs / np.sum(freqs)
print(wghts)

rng = np.random.default_rng(1357907531)

counter = np.zeros(len(items))

N = 1000000

for k in range(0, N):
    u01 = rng.random(len(items))
    ki  = np.power( u01 , 1.0/wghts)
    q = np.argsort(ki)
    
    counter[q[-1]] += 1

print(counter/np.sum(counter))

    它打印标准化权重

    [0.00083126 0.00083126 0.00083126 0.16625104 0.8312552]

    并用于抽样测试

    [8.36000e-04 8.19000e-04 8.55000e-04 1.65964e-01 8.31526e-01]

    漂亮的算法，适用于流式、水库式采样，m from n采样你能想到的。

    更新二

    这是 Java 中 WRS 实现的另一个链接，它是由 Efraimidis 完成的不同变体。

    https://utopia.duth.gr/~pefraimi/projects/WRS/

    快速复杂性分析

    有一次生成n个随机数，时间为 n*T RNG，O(n)

    还有另一遍，我们计算 u01 的逆权重幂，幂由 log&exp 调用 n*(T log +T exp ), O(n)

    如果循环是手动完成的，而不是通过某些矢量化库（如 numpy）完成的，则可以将它们组合起来。

    最后一步是排序，时间复杂度为 O(n log(n))，对于较大的n，此项将占主导地位，使得 WRS 算法复杂度为 O(n log(n))

    • 0

相关问题