一种简单的生成伪随机数的方法（翻译）

这个算法来源于 （(北京交通大学中国铁道科学研究院)）：/p-5405273318696.html

简介：这个算法是用来生成随机订单号的算法。

对于这个算法，自己的理解以及代码实现：/star1210644725/article/details/100169386

原文是英文版的，自己英语不太好，就用有道词典翻译了一下：

一种简单的生成伪随机数的方法

PanXianzhong(北京交通大学中国铁道科学研究院)

文摘:介绍了一种新方法叫做Disordering-Digit法(DDM)生成随机数,这不仅可以产生数字随机也不可重复的不同于其他RNG(随机数生成)方法以数学或物理手段,DDM很简单实现,可以运行在非常高的速度在计算机编程。简单和不可重复是DDM最突出的两个特性。最后给出了DDM的具体实现方法，并对其良好的统计特性进行了描述，最后给出了DDM在中国订票系统中生成旅客订单号的实例

关键词:随机数，数字无序，不可重复，订票系统

1 Introductior

随机数在许多信息系统中得到了广泛的应用。数学和计算机科学中已有许多生成随机数的算法和物理生成器，如同余算法、Fibonacci和Tausworthe序列、多素数生成器和混沌映射[1]。然而，几乎所有的算法都不能保证长时间内不生成相同的数字，生成的数字都是“伪随机数”。物理发生器可以产生真正的随机数，这些随机数是绝对不可预料和不可重复的，但它严重依赖于材料和环境等许多内部和外部因素，实现起来非常不容易。DDM是根据一个不断增长的连续数字序列对数字的数字进行无序排列，从而产生随机数。没有任何复杂的数学公式和函数，无序规则是很容易理解的，可以作为一个足够快的手段在许多情况下。虽然DDM产生的数字是伪随机数，但是根据一定的已知规则。它们在两个特征上与真随机数相同。首先，生成的每个数字在其最大值范围内不会出现超过一次。第二，它们是均匀分布的，没有周期规律。

2 DDM

算法细节对连续数的数字进行无序排列是DDM的基本算法。该方法的三个tep分别为:

生成连续数字对于任何信息系统，都很容易生成连续的数字，例如Sybase数据库表的标识列以及各种计算机计数器。如果我们想要在(1.999)中得到不可重复的数字，通常的方法是从1到999依次生成数字，即这样一个数组:1.2.3.4……97.998,999。它们绝对是不可重复的，但绝不是随机的。每个人都知道下一个数字是什么。

制定一个顺序数字规则如我们所知，数字是由数字组成的，称为单位'数字，十'数字等。例如，数字417有三个数字，单位的数字是7，十位的数字是1，百位的数字是4。如果我们想要数字417呈现一个完全不同的面貌，我们不需要改变所有的数字，我们只需要打乱它们。如果无序规则是“个位移到十位，十位移到百位，百位移到个位”，那么我们得到一个新的174。

关于这个无序规则有两个问题。首先，我们不能用同样的规则打乱所有的数字。选择以下5个数字作为示例:123,124,125,126,127。如果我们用同样的规则对他们的数字进行排序，比如“单位的数字移到十位，十位移到百位，百位移到单位位”，结果是:231,241,251,261,271。显然，我们可以很容易地猜到下一个数字是281。其次，我们也不能用完全不同的规则来扰乱它们。选择以下两个数字作为示例:123,321。如果我们障碍1由“单位搬到十位,十位搬到几百的数字,几百位搬到单位的数字”规则,和混乱3由“单位的数字搬到单位的数字,十位搬到几百的数字,几百位搬到十位数”规则,然后我们得到同样的结果:231年。根据这个规则，231会出现两次。如果是这样，无序的数字就不是

首先，我们用不同的规则打乱它们。其次，对于那些数字和相等的数，我们用同样的规则对它们进行排序。以上面的例子为例，我们把123和321按照相同的“单位数移到十位，十位移到百位，百位移到单位数”的规则排列得到231和213。它们都是不可预料和不可重复的。为了遵守以上两条规则，我们应该用不同的排列组合尽可能多地制定不同的无序规则，并确保相同的规则适用于相同的数字和数字。对于I到999之间的数字，最大的数字999是一个3位的数字。当我们通过在小于3位的umber的最前面加上0(比如1变成001,12变成012)来得到所有由3位组成的数之后，我们就有了3位来打乱所有的f。三个位有6个排列组合:123.132.213.231.312.321。所以我们最多有六条无序规则。假设1代表单位位，2代表十位，3代表百位，这六条规则被描述为:123:单位位移动到百位，十位移动到十位，百位移动到单位位。132:单位数移到百位，百位移到十位，十位移到单位数。213:十位移到百位，个位移到十位，百位移到个位。231:十位移到百位，百位移到十位，个位移到个位。312:百位移到百位，个位移到十位，十位移到个位。321:百位移动到百位，十位移动到十位，单位移动到单位。

在实际情况下，如何将失序判定为一个不为人知的秘密规则

产生的连续数的无序在制定了无序规则之后，我们将它们应用于每一个产生的连续数字。以(1999)中的数字为例，每一个数字都可以被六条规则中的一条打乱。规则和结果如表2-1所示。

3 DDM产生随机数的统计特征

好的随机数具有均匀分布、独立、周期长、速度快、效率高等统计特性。首先，DDM产生的随机数在一定范围内均匀分布。其次，在无序之前，它们是连续的。但经过不同的无序。规则是不可预料的，它们之间没有任何关系。第三，周期与最大值一样长。也就是说，(1.999)中的随机数在999之后会重复。在它的周期中，每个数字只出现一次。第四，没有任何复杂的计算，DDM能显著提高效率也就不足为奇了。

4、DDM的一个真实案例

订票系统(TRS)是一种旅客输入出行需求，如发车日期、发车城市、目的地城市、指定列车、座位类型、票号等信息的订票系统。然后系统根据需求因素占有特定的席位。如果占领成功，系统将以订单形式记录旅行信息的详细信息，并向乘客提供订单号。其他时间在售票处提供订单号，乘客可以获得纸质车票作为乘车证。

如何生成订单号曾经是一个两难的问题。订单号作为唯一的购票密钥，实际上是购票密码。不可猜测是必要的特性。此外，不同的数字代表不同的票，相同的数字必须对应相同的票。如果系统为两个以上不同的乘客生成相同的订单号，他们在索要纸质机票时会感到困惑。因此不可重复是TRS 4.0版本的另一个必要特性，订单号由Sybase数据库现有的rand()函数生成。这是随机的，但同样的数字偶尔会出现两次或更多，票务代理必须与乘客确认旅行细节，以便挑选出正确的号码。为了避免这个问题，在TRS的5.0版本中。订单号连续生产。这是不可重复的，但也是可以猜测的。订单37511936的乘客可能很容易猜到之前的订单37511935。37511934等。然后，他/她将通过提供猜测的订单号来获取其他乘客的机票。为了解决这个问题，在5.0版本中，在预订过程中需要一个来自乘客的真实密码。要打印纸质票，需要订单号和密码。在这种情况下，乘客必须一次性记住订单号和密码

由于时间每毫秒都在增长，直接使用当前计算机的日期和时间作为订单号是一种看似可行的方法，比如07181138420。但是计算机系统的最小时间片是毫秒，并且在仅仅一毫秒内，就保留了一百多个订单。此外，用这种方法产生的数字太长。

DDM是一种生产TRS订单号的合适方法。假设我们想要8位的序号。

首先，我们创建一个数据库表来生成和保存每个预订业务的连续编号。表A的一列被设置为标识列。它可以自我增长。每次插入一行时间隙为1。我们为列设置了一个初始值，比如12345678。然后每次预约操作，我们都得到连续的数字:12345678,12345679,12345680,12345681,12345682…直到99999999类推。

其次，对表生成的8位数字进行无序化处理。8位有8*7*6*5*4*3*2*1 = 40320个排列组合。8位数字的最大个数是99999999，所以8位数字的最大和是9+9+9+9+9+9+9+9 +9+9 = 72。我们从40320个排列和组合中随意制定了72条无序规则，如81654237、72345618、62345178、53271468、85732146等。

根据数字的和，我们将72条无序规则中的一条应用于生成的连续数。为例。我们打乱了上面提到的五个连续数字:12345678、12345679、12345680、12345681、12345682。表4-1列出了这些数字的和以及它们所应用的无序规则，以及新数字的结果。

在这种情况下，我们可以很容易地得到I到99999999之间的随机和不可重复的数字，在试运行过程中，效果非常令人满意。在4.0和5.0版本中出现的问题都得到了很好的解决。然后，这种方法被推广到铁路订票的其他渠道，如电话、互联网和短信。我们希望它在TRS方面的成功将使其在其他信息系统中得到广泛的应用。

参考文献

1杨子强，魏恭义，<几种新的兰德数生成方法的研究综述>，《数值计算》《方法与计算机应用》，2001年9月，第3期在对团购票销售与预订系统进行研究，总结了团购票预订系统的设计规范。北京，中国铁道科学研究院，3售票订票系统研究小组，中铁车站订票系统V5.0操作手册，北京，中铁出版社，