草庐IT

c++ - 保证值序列所有可能排列的伪随机分布 - C++

coder 2024-02-22 原文

随机问题。

我正在尝试创建一个程序来生成伪随机分布。我正试图找到适合我需要的伪随机算法。这些是我的担忧:

1) 我需要一个输入来在每次使用时生成相同的输出。

2) 它需要足够随机，以至于查看输入 1 的输出的人看不到输入 1 的输出与输入 2 的输出之间没有任何联系(等等)，但不需要密码安全或真正随机。

3)它的输出应该是一个介于 0 和 (29^3200)-1 之间的数字，该范围内的每个可能的整数都是一个可能的且同样(或接近)可能的输出。

4) 我希望能够保证 410 个输出序列的每个可能排列也是连续输入的潜在输出。换句话说，0 到 (29^3200)-1 之间的 410 个整数的所有可能分组应该是顺序输入的潜在输出。

5) 我希望该函数是可逆的，这样我就可以取一个整数或一系列整数，并说明哪个输入或哪个输入系列会产生该结果。

到目前为止我开发的方法是通过一个简单的哈尔森序列运行输入:

boost::multiprecision::mpz_int denominator = 1;
boost::multiprecision::mpz_int numerator = 0;

while (input>0) {
    denominator *=3;
    numerator = numerator * 3 + (input%3);
    input = input/3;
}

并将结果乘以 29^3200。它满足 1-3 的要求，但不满足 4 的要求。而且它只对单个整数是可逆的，对序列不是可逆的(因为不是所有的序列都可以由它产生)。我在 C++ 中工作，使用 boost multiprecision。

如果有人能给我任何关于生成满足这些要求的随机分布的方法的建议，或者只是一类值得为此研究的算法，我们将不胜感激。预先感谢您考虑我的问题。

----更新----

由于多个评论者都关注所讨论数字的大小，我只是想明确表示，我认识到使用此类集合会带来实际问题，但在提出这个问题时，我只对理论或概念感兴趣解决问题的方法 - 例如，想象一下使用更小的整数集(如 0 到 99)以及 10 个输出序列集的排列。你将如何设计一个算法来满足这五个条件 - 1)输入是确定的，2)随机出现(至少对人眼而言)，3)范围内的每个整数都是可能的输出，4)不仅是所有值，而且值序列的所有排列都是可能的输出，5)函数是可逆的。

---第二次更新---

非常感谢@Severin Pappadeux，我能够反转 lcg。我想我会补充一点我所做的，希望能让任何人在未来更容易看到这一点。首先，这些是反模函数的极好资源:

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses

https://www.khanacademy.org/computer-programming/discrete-reciprocal-mod-m/6253215254052864

如果您采用等式 next=ax+c%m，将以下代码与您的 a 和 m 值一起使用，将打印出您需要求逆的欧几里德方程，以及逆的值:

    int qarray[12];
    qarray[0]=0;
    qarray[1]=1;
    int i =2;
    int reset = m;
    while (m % a >0) {
      int remainder=m%a;
      int quotient=m/a;
      std::cout << m << " = " << quotient << "*" << a << " + " << remainder << "\n";
      qarray[i] =qarray[i-2]-(qarray[i-1]*quotient);
      m=a;
      a=remainder;
      i++;
  }
if (qarray[i-1]<0) {qarray[i-1]+=reset;}
std::cout << qarray[i-1] << "\n";

我花了一段时间才弄清楚的另一件事是，如果你得到一个否定的结果，你应该加上 m。您应该在新等式中添加一个类似的项:

prev = (ainverse(next-c))%m;
if (prev<0) {prev+=m;}

我希望这对 future 走这条路的人有所帮助。

最佳答案

好吧，我不确定是否有一个通用的答案，所以我会专注于具有 64 位内部状态/种子、产生 64 位输出并具有 2^64-1 周期的随机数生成器。特别是，我会以 

next = (a * prev + c) mod m

哪里a和 m互为质数

所以:

1) 检查

2) 检查

3) 检查(好吧，当然是针对 64 位空间)

4) 检查(同样，除了 0 我相信，但是 64 位的每一个排列都是从一些种子开始的 LCG 的输出)

5) 检查。众所周知，LCG 是可逆的，即可以得到 

prev = (next - c) * a_inv mod m

其中 a_inv 可以从 a 计算得出, m使用欧几里得算法

好吧，如果你觉得没问题，你可以尝试在你的 15546 位空间中实现 LCG

更新

快速搜索在此处显示可逆 LCG 讨论/代码

Reversible pseudo-random sequence generator

关于c++ - 保证值序列所有可能排列的伪随机分布 - C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29569927/

amp43code可逆的c++algorithmrandompermutationlcg

有关c++ - 保证值序列所有可能排列的伪随机分布 - C++的更多相关文章

  1. 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

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. 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][

  4. 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

  5. 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

  6. 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

  7. ruby - 获取模块中定义的所有常量的值 - 2

    我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

  8. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  9. ruby - 分布式事务和队列，ruby，erlang，scala - 2

    我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和

  10. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

随机推荐