jjzjj

javascript - Fisher-Yates 洗牌可以产生所有纸牌排列吗？

coder 2024-05-16 原文

我正在使用标准的 Fisher-Yates 算法随机洗牌数组中的一副牌。但是，我不确定这是否真的会产生真实世界洗牌后所有可能排列的真实分布。

V8 的 Math.random 只有 128 位的内部状态。由于一副牌中有 52 张牌，52 阶乘将需要 226 位的内部状态来生成所有可能的排列。

但是，我不确定这在使用 Fisher-Yates 时是否适用，因为您实际上并没有生成每个可能的位置，而只是从 52 个中随机获得一个位置。

function shuffle(array) {
  var m = array.length, t, i;

  while (m) {
    i = Math.floor(Math.random() * m--);
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

最佳答案

一般来说，如果伪随机数生成器允许少于 52 个不同的阶乘种子，那么在打乱 52 项列表时，特定的 PRNG 无法选择一些排列，而 Fisher-耶茨无法改变这一点。 (一个特定 PRNG 可以选择的排列集可以不同于另一个 PRNG 可以选择的排列集，即使两个 PRNG 都使用相同的种子进行初始化。)另请参见 this question。 .

请注意，尽管在撰写本文时 V8 使用的 Math.random 算法允许大约 2^128 个种子中的任何一个，但是 Math.random，仅声明该方法使用“依赖于实现的算法或策略”来生成随机数(请参阅 ECMAScript sec. 20.2.2.27)。

PRNG 的周期可以通过 Bays-Durham 洗牌来延长，这有效地增加了 PRNG 的状态长度(参见 Severin Pappadeux 的回答)。但是，如果您仅使用 PRNG 的输出初始化 Bays-Durham 表条目(而不是使用种子来初始化这些条目)，那个特定的 PRNG(包括它初始化这些条目并根据它生成的随机数选择这些表条目的方式)不能选择比初始化其原始状态的可能种子数更多的排列，因为只有一种方法可以初始化 Bays-给定种子的 Durham 条目——当然，除非 PRNG 实际上洗牌的列表数量过多，以至于它在没有循环的情况下生成的随机数比没有 Bays-Durham 洗牌的随机数更多。

例如，如果 PRNG 的长度为 128 位，则只有 2^128 个可能的种子，因此只有 2^128 种方法可以初始化 Bays-Durham 洗牌，每个种子一种，除非超过 128 位的种子扩展到 Bays-Durham 表条目，而不仅仅是 PRNG 的原始状态。 (这并不意味着 PRNG 可以选择的排列集总是相同的，无论它如何选择 Bays-Durham 洗牌中的表条目。)

编辑(8 月 7 日):澄清。

编辑(2020 年 1 月 7 日):已编辑。

关于javascript - Fisher-Yates 洗牌可以产生所有纸牌排列吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57332878/

纸牌洗牌条目种子javascriptarraysrandomshuffle

有关javascript - Fisher-Yates 洗牌可以产生所有纸牌排列吗？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  3. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  4. ruby - 我可以使用 Ruby 从 CSV 中删除列吗？ - 2

    查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html

  5. ruby - 我可以使用 aws-sdk-ruby 在 AWS S3 上使用事务性文件删除/上传吗？ - 2

    我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的

  6. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  7. ruby-on-rails - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

  8. ruby - Nokogiri 剥离所有属性 - 2

    我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？ 最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog

  9. ruby - 按值降序排列散列，然后按升序键入 ruby - 2

    我有这样的哈希trial_hash={"key1"=>1000,"key2"=>34,"key3"=>500,"key4"=>500,"key5"=>500,"key6"=>500}我按值降序排列:my_hash=trial_hash.sort_by{|k,v|v}.reverse我现在是这样理解的:[["key1",1000],["key4",500],["key5",500],["key6",500],["key3",500],["key2",34]]但我希望当值相同时按键的升序排序。我该怎么做？例如:上面的散列将以这种方式排序:[["key1",1000],["key3",500

  10. ruby - 有人可以帮助解释类创建的 post_initialize 回调吗 (Sandi Metz) - 2

    我正在阅读SandiMetz的POODR，并且遇到了一个我不太了解的编码原则。这是代码:classBicycleattr_reader:size,:chain,:tire_sizedefinitialize(args={})@size=args[:size]||1@chain=args[:chain]||2@tire_size=args[:tire_size]||3post_initialize(args)endendclassMountainBike此代码将为其各自的属性输出1,2,3,4,5。我不明白的是查找方法。当一辆山地自行车被实例化时，因为它没有自己的initialize方法

随机推荐