问题标签 [fisher-yates-shuffle]

有像 FisherYates 这样的洗牌算法。他们接受一个数组并以随机顺序返回一个元素。这在 O(n) 中运行。

我正在尝试做的是实现一个优先的 left-shuffle algorithm。这意味着什么？

• Prioritized：它不采用值数组。它需要一组价值-概率对。例如[ (1, 60), (2, 10), (3, 10), (4, 20) ]。值 1 有 60%，值 2 有 10%，...
• left-shuffle：一个值的概率越高，它在数组左侧的机会就越大。

我们以这个例子为例[ (1, 10), (2, 10), (3, 60), (4, 20) ]。最可能的结果应该是[ 3, 4, 1, 2 ]或[ 3, 4, 2, 1 ]。

我尝试实现这一点，但在 O(n) 中没有找到任何解决方案。

基于 FisherYates 的伪代码中的 O(n^2)：

什么可能会改善这一点：在一开始就按概率对元素进行排序，以最小化交换次数和内部循环中的迭代。

有没有更好的解决方案（甚至可能在 O(n) 中）？

我在这里找到了关于 Fisher-Yates 和随机化的非常有趣的东西：如何随机化（随机播放）JavaScript 数组？

内容！

现在我想用名字替换这 30 位数字（例如：Thomas、Adrian、James、Patrick、Victor...）

我怎样才能做到这一点？我对此很陌生，我迈出了第一步

我正在查看一个问题，该问题是关于 Fisher-Yates 洗牌算法的错误实现，我很困惑，当实施不正确时存在偏差。

这两种算法是：

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

良好的实施：

糟糕的实现：

为了清楚地了解这些图，我从数字 0 到 99 开始，使用任何一种算法创建 10_000_000 个随机播放，然后对每个随机播放中的值进行平均以获得一组数字。如果洗牌是随机的，那么所有 100 个数字都属于同一个正态分布。

现在，一切都很好，但我想我会检查这些方法是否产生有效的结果：

两者都很好，但它们是公平的洗牌吗？

OrderByRandomNext：

OrderByRandomNextDouble：

注意到1和100数字在每个中都显着降低了吗？

好吧，我认为这可能是如何OrderBy工作的人工制品。所以我用另一个随机数生成器对其进行了测试——Eric Lippert 在他改进的随机系列中使用了一个。

好吧，这是图表：

没有偏见！

这是我生成数据的代码（在 LINQPad 中运行）：

这是我生成的数据：

这是我的问题。发生了什么System.Random以及它引入的偏见？

感谢@axtck对Fisher Yates 随机化的帮助，他帮助我在这里将数字变成了单词：

由于 shuffle 函数对数组索引进行了随机播放，因此您可以像以前一样对数组进行随机播放，但在数组中添加名称字符串。

代码现在显示一串用逗号分隔的单词，它运行良好！

现在我想用空格替换逗号（例如：Histoire Chien Koala Arbre Italique Lampadaire Docteur Boulet Maison Forge Gagnant Ennui）

有人可以帮我用空格更改这些逗号吗？

谢谢

假设我有一个这样的数组。

我如何洗牌，但所有的值都相等？

洗牌后的示例预期输出：

我一直在做一个项目。部分项目需要一个混洗链表。这个函数是fisher-yates shuffle算法的一个实现。它将链表放入一个数组中。然后它洗牌。然后重新链接它。

经过一些测试，我发现有时当我对链表进行洗牌时，我会在某处丢失一个节点。我用 ubsan 和 asan 做了一些测试。他们都没有表现出任何东西。我曾经遇到过这个函数的问题，后来导致了段错误。段错误是由于未正确重新链接链表而引起的。更具体地说，链表中改组之前的最后一个节点未正确重新链接。我通过在改组之前使列表循环来解决这个问题。

以下是用于混洗以及交换和重新链接功能的代码：

我被一个明显简单的问题困住了。我编写了一个子例程，它接受一个长度数组n和另一个数字m作为输入，然后输出一个大小m为包含从原始数组中均匀随机选择的数字的数组。我可以传递replace=False选项，然后输出数组中的数字总是不同的，因为原始数组中没有重复。我的问题是，我可以使用相同的例程随机打乱数组吗？乍一看，如果我输入m=n. 问题是我不确定这是否会以相等的概率输出输入数组的所有可能排列（尽管如果不是，我会感到惊讶！）。如果这没有发生，我将为 Fisher-Yates shuffle 编写另一个例程。

当我想从 [1...n] 中对数组“perm”中的数字数组进行洗牌时，我用 Java 写道：

但是本书将随机化代码编写为（仅在 for 循环中进行了更改）：

他们说，通过他们编写的代码，他们通过从尚未选择的牌中统一选择来确保洗牌是随机的。（与我的方法相反，我从所有卡片中选择）。（我相信这是他们写的Fisher-Yates算法的修改版本）。

我只想知道我的代码（上面的代码）对于随机数生成是否也无偏见？如果是，为什么？如果不是，为什么？

（前 2 条评论是针对我问我所做的是否适合随机数生成的问题，但我想问它是否公正。但我当时不知道这个术语，抱歉。对于这个当前问题，第4条评论有一个很好的理解链接）。

我有一个包含 50 个对象的数组作为元素。

每个对象包含一个由 4 个元素组成的数组：

我想随机选择 10 个元素并保存到另外两个数组中，这是我想要随机播放选项的数组之一。但是在洗牌时，两个数组都会受到影响。

我该如何防止呢？

我觉得我错过了一些非常简单的东西，但我无法发现它。

我将此作为指南，但我认为我的实现有问题。 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

我正在尝试使用整个甲板作为一个池来洗牌的前 5 张牌，但只洗牌前 5 张牌。

这是我的代码：

编辑：

您不需要 ShuffleDeck() 中的 while 循环，只需使用 random = cardIndex + GetRandomNumber(NUM_CARDS_IN_DECK - cardIndex) 并无条件交换。– G.斯莱彭

这实际上解决了我的问题。