标签: fisher-yates-shuffle

我正在看一个问题，该问题讨论的是 Fisher-Yates shuffle 算法的错误实现，但我对错误实现时存在偏差感到困惑。

这两个算法是：

private Random _random = new Random();

public int[] FisherYates(int[] source)
{
    int[] output = source.ToArray();
    for (var i = 0; i < output.Length; i++)
    {
        var j = _random.Next(i, output.Length);
        (output[i], output[j]) = (output[j], output[i]);
    }
    return output;
}

public int[] FisherYatesBad(int[] source)
{
    int[] output = source.ToArray();
    for (var i = 0; i < output.Length; i++)
    {
        var j = _random.Next(0, output.Length);
        (output[i], output[j]) = (output[j], output[i]);
    }
    return output;
}

一个非常微妙的不同，但足以引起巨大的偏见。

良好的实施：

错误的实现： …

我正在尝试编写一个 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 …

我想要一个采用以下参数的字符串改组算法：

void CRLimitedShuffle(char* Str, uint8_t MaxConsecutiveRepetition);

该函数应对输入字符串执行随机洗牌。然而：

• 必须遵守限制MaxConsecutiveRepetition，即结果字符串中最多MaxConsecutiveRepetition允许出现连续的相同字符。
• 所有正确的洗牌结果必须以相同的概率出现。

例如：

Str="aaaaabbbbb";
MaxConsecutiveRepetition=3;

对于上面的参数，“aabbbaaabb”是正确的结果，而“aaabaabbbb”是不正确的，因为它有 4 个连续的“b”，超过MaxConsecutiveRepetition。

一个天真的想法是对打乱的结果进行审核，如果不符合要求就重新打乱。然而，对于某些极端情况，性能可能会极低。例如：

Str="aaaabbbbbbbbbb";
MaxConsecutiveRepetition=2;

在这个例子中，只有“bbabbabbabbabbabb”是正确的输出，所有其他随机生成的序列都被丢弃。这样，函数就会不断循环，直到以很小的概率生成唯一的正确字符串。

另一个想法是生成所有可能的排列，然后消除那些错误的排列，并从剩余的正确排列中随机抽取。但该算法的复杂度将是阶乘的。

最终的想法是对 Fisher-Yates 进行数学修改：从随机字符开始，然后每次绘制下一个字符时，将前一个字符被绘制的概率乘以衰减系数。例如，如果前一个字符已连续绘制了MaxConsecutiveRepetition多次，则衰减系数应变为0，以确保下一个字符不能与前一个字符相同。然而，我不知道如何准确计算这个衰减系数以确保以相等的概率生成所有正确的排列。

我需要一个满足上面列出的两个要求的算法。