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

2023-09-11 22:44:13 作者：夏雪若

随机的问题。

我试图创建一个程序，这将产生一个伪随机分布。我试图找到合适的伪随机算法满足我的需求。这是我所关心的：

I am attempting to create a program which would generate a pseudo-random distribution. I am trying to find the right pseudo-random algorithm for my needs. These are my concerns:

1），我需要一个输入每次使用的时间，以产生相同的输出。

1) I need one input to generate the same output every time it is used.

2）它必须是足够随机，一个人谁看起来在输出从输入1看到，并且之间没有连接从输入2（等）的输出，但没有必要为它是加密安全或真正随机的。

2) It needs to be random enough that a person who looks at the output from input 1 sees no connection between that and the output from input 2 (etc.), but there is no need for it to be cryptographically secure or truly random.

3）它的输出应是一个介于0和（29 ^ 3200）-1，并在该范围内的每一个可能的整数一个可能的和相等（或接近）可能输出

3)Its output should be a number between 0 and (29^3200)-1, with every possible integer in that range a possible and equally (or close to it) likely output.

4）我想是能够保证的410输出序列的每一种可能的置换也是连续输入的电势输出。换句话说，在0和（29 ^ 3200）410的整数的所有可能的分组-1应该是连续的输入输出电位

4) I would like to be able to guarantee that every possible permutation of sequences of 410 outputs is also a potential output of consecutive inputs. In other words, all the possible groupings of 410 integers between 0 and (29^3200)-1 should be potential outputs of sequential inputs.

5）我想的功能是可逆的，这样我就可以采取整数或整数系列，并说其中输入输入或一系列会产生的结果。

5) I would like the function to be invertible, so that I could take an integer, or a series of integers, and say which input or series of inputs would produce that result.

我已经开发到目前为止，其方法是通过一个简单的halson顺序运行，输入：

The method I have developed so far is to run the input through a simple halson sequence:

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 ++中，使用升压多precision。

and multiply the result by 29^3200. It meets requirements 1-3, but not 4. And it is invertible only for single integers, not for series (since not all sequences can be produced by it). I am working in C++, using boost multiprecision.

任何意见，有人可以给我关于一个方法来生成一个随机分布满足这些要求，或只是一类的算法值得为此研究，将大大AP preciated。感谢您提前考虑我的问题。

Any advice someone can give me concerning a way to generate a random distribution meeting these requirements, or just a class of algorithms worth researching towards this end, would be greatly appreciated. Thank you in advance for considering my question.

----更新----

----UPDATE----

由于多种批评家都集中在有问题的数字的大小，我只是想清楚，我认识的实际问题，与这样的集合姿势，但在问这个问题的工作，我只是在理论或概念有兴趣解决问题的方法 - 例如，假设有一组整数小得多如0到99，套10输出序列的排列工作。如何设计一种算法来满足这些五个条件 - 1）输入是确定性的，2）出现随机（至少对人眼），3）的范围内的每个整数是一个可能的输出，4）不仅所有的值，也值序列的所有排列都是可能的输出，5）函数是可逆的。

Since multiple commenters have focused on the size of the numbers in question, I just wanted to make clear that I recognize the practical problems that working with such sets poses but in asking this question I'm interested only in the theoretical or conceptual approach to the problem - for example, imagine working with a much smaller set of integers like 0 to 99, and the permutations of sets of 10 of output sequences. How would you design an algorithm to meet these five conditions - 1)input is deterministic, 2)appears random (at least to the human eye), 3)every integer in the range is a possible output, 4)not only all values, but also all permutations of value sequences are possible outputs, 5)function is invertible.

---第二次更新---

---second update---

许多感谢@Severin Pappadeux我能反转的LCG。我想我要补充一点关于我做了什么，希望能够使它更容易为任何人在将来看到这一点。首先，这些都是优秀的来源上反转的模块化功能：

with many thanks to @Severin Pappadeux I was able to invert an lcg. I thought I'd add a little bit about what I did to hopefully make it easier for anyone seeing this in the future. First of all, these are excellent sources on inverting modular functions:

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

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

如果你把公式下一= AX + C％M，用下列code与你的价值观为a和m将打印出你需要找到ainverse欧氏公式，还有ainverse的价值：

If you take the equation next=ax+c%m, using the following code with your values for a and m will print out the euclidean equations you need to find ainverse, as well as the value of ainverse:

    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";

其他的事情，我花了一段时间才能弄清楚的是，如果你得到了否定的结果，你应该添加米到它。您应该添加一个类似的术语来新的公式：

The other thing it took me a while to figure out is that if you get a negative result, you should add m to it. You should add a similar term to your new equation:

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

我希望帮助任何人谁冒险沿着这条道路的未来。

I hope that helps anyone who ventures down this road in the future.

推荐答案

好吧，我不知道是否有一个普遍的答案，所以我会专注于有，比如说随机数生成器，64位内部状态/种子生产64位输出，并有2 ^ 64-1期。特别是，我会看着线性同余发生器（又名LCG）的形式

Ok, I'm not sure if there is a general answer, so I would concentrate on random number generator having, say, 64bit internal state/seed, producing 64bit output and having 2^64-1 period. In particular, I would look at linear congruential generator (aka LCG) in the form of