{询问}{算法}生成不重复未随机数的算法

[四不象]

有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。

 

或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱

[Shuo Chen]

std::shuffle

[王加冕]

数据离散度较好(分布比较均匀)的要求是违背"随机"的吧？ 随机并非均匀分布，只有数据量足够大时它们的分布才是比较均匀的。

在 09-8-11，四不象<tabri...@gmail.com> 写道：

> 有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。
>
> 或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱

--
Kind Regards,
Jammy | 王加冕，http://www.geektu.com/
367# Mailbox, Institute of Mathematics, Shandong University, 27#
Shanda Nan Rd, Shandong, China. (250100)

[applejues]

王加冕 wrote:
> 数据离散度较好(分布比较均匀)的要求是违背"随机"的吧？ 随机并非均匀分布，只有数据量足够大时它们的分布才是比较均匀的。
>
> 在 09-8-11，四不象<tabri...@gmail.com> 写道：
>
>> 有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。
>>
>> 或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱
>>
>
>
>

数据结构与算法分析上的例子是
for(int i=0;i<N;++i)
a[i]=i+1;
for(int i=0;i<N;++i)
swap(a[i],a[rand(0,i)]);

[Wenbo Yang]

"Programing Pearls" Column 11 讨论了类似的问题。

文博

2009/8/11 四不象 <tabris17.cn@gmail.com>

有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。

 

或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱

--
Wenbo YANG

Homepage ---> http://solrex.cn
Blog | Solrex Shuffling ---> http://blog.solrex.cn

[rockeet]

有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。

----随机分布，不重复，是相互矛盾的需求

或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱
----这个问题，跟上一个问题并不等价，去看看 std::random_shuffle 的源码

[jrckkyy]

前几天看了个类似的算法希望对你有帮助 生成随机数的一个可靠算法，高质量的均匀分布的随机函数

2009/8/11 四不象 <tabris17.cn@gmail.com>

有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。

 

或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱

--
http://hi.baidu.com/jrckkyy

[Ian Yang]

Boost.Random有比较详细的文档说明了几种流行的随机数算法

-------
Sincerely, Ian Yang

2009/8/12 jrckkyy <jrc...@gmail.com>

[四不象]

好像这些随机数生成算法不能保证不重复

[DaiZW]

如果你要打乱一个有序数组就直接这样好了:

random.seed()

while True;
list.swap( random.randint(0, listlength-1), random.randint(0,
listlength-1) )

一直循环到你满意为止.

2009/8/12 四不象 <tabri...@gmail.com>:

> 好像这些随机数生成算法不能保证不重复
>
> ----- Original Message -----
> From: jrckkyy
> To: pon...@googlegroups.com
> Sent: Wednesday, August 12, 2009 12:44 AM
> Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法
> 前几天看了个类似的算法希望对你有帮助 生成随机数的一个可靠算法，高质量的均匀分布的随机函数
>

> 2009/8/11 四不象 <tabri...@gmail.com>

[Shuo Chen]

这么做是错的，因为结果并不均匀。TAOCP专门讲了shuffle算法的各种错误变型，包括你这种。

前面一位老兄给出了正确的算法。

[Shuo Chen]

[Shuo Chen]

如果rand(0, x)返回闭区间[0, x]中均匀分布的随机整数，那么就是对的。

[Wenliang]

http://en.wikipedia.org/wiki/Linear_congruential_generator

四不象 wrote:

好像这些随机数生成算法不能保证不重复

----- Original Message -----

From: jrckkyy

To: pon...@googlegroups.com

Sent: Wednesday, August 12, 2009 12:44 AM

Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法

前几天看了个类似的算法希望对你有帮助 生 成随机数的一个可靠算法，高质量的均匀分布的随机函数

[四不象]

英文看起来比较辛苦，线性同余可以保证生成随机数不重复？

----- Original Message -----

From: Wenliang

To: pon...@googlegroups.com

Sent: Wednesday, August 12, 2009 11:05 AM

Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法

http://en.wikipedia.org/wiki/Linear_congruential_generator

四不象 wrote:

好像这些随机数生成算法不能保证不重复

----- Original Message -----

From: jrckkyy

To: pon...@googlegroups.com

Sent: Wednesday, August 12, 2009 12:44 AM

Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法

前几天看了个类似的算法希望对你有帮助 生成随机数的一个可靠算法，高质量的均匀分布的随机函数

[David Gao]

有很多成熟的算法，你可以看看。
我认为，伪随机数算法生成的随机数是有可能出现重复的。
我觉得，有个应用的前提：（1）你需要的随机数算法多久产生一次，例如一秒钟，一分钟。（2）你的随机数有多长。是32位，还是64位。还是其他。
不同的应用需求可以使用不同的算法。

例如，如果你对长度和生成频率没有要求，你可以直接将从Epoch开始的秒数左移+微妙数。

《游戏编程精粹2》里面讲过一种据说是真随机的算法，大致是，找到一些非常混乱的物理源（也就是数字啦，例如内存数据，最近几次键盘的输入，声卡参数等等），然后用一个比较好的混合函数（例如MD5），将这些混乱源混合，就得到一个比较好的随机数。

或者考虑UUID之类的。

一点浅见，希望有用处。

--
David Gao

[四不象]

谢谢啦

[Wenliang]

可以。但要满足一定条件，
比如a=5, b=3, c=0, x0 = 7, m=8
x1 = (5*7 + 3) % 8 = 6
x2 = (5*6 + 3) % 8 = 1
x3 = (5*1 + 3) % 8 = 0
x4 = (5*0 + 3) % 8 = 3
x5 = (5*3 + 3) % 8 = 2
x6 = (5*2 + 3) % 8 = 5
x7 = (5*5 + 3) % 8 = 4

所以就随机选择满足条件的a, b, c, 初始值吧

[Shuo Chen]

只要随机数的长度是有限的，没有哪个算法能保证不重复，MD5都有重复的呢。

如果随机数的集合不大，那么每次随机选取一个集合中的数，并把它从集合中去掉，这样肯定是不重的。不过取完就没了。

如果随机数的集合比较大，简单的办法就是搞个数据库的表（条件合适也可以用hash set），只有一列，是个unique key，每次生成的随机数
插入数据表，如果插不进去，表明已经用过了。

四不象 wrote:
> 英文看起来比较辛苦，线性同余可以保证生成随机数不重复？
> ----- Original Message -----
> From: Wenliang
> To: pon...@googlegroups.com
> Sent: Wednesday, August 12, 2009 11:05 AM
> Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法
>
>
> http://en.wikipedia.org/wiki/Linear_congruential_generator
>
> 四不象 wrote:
> 好像这些随机数生成算法不能保证不重复
> ----- Original Message -----
> From: jrckkyy
> To: pon...@googlegroups.com
> Sent: Wednesday, August 12, 2009 12:44 AM
> Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法
>
>
> 前几天看了个类似的算法希望对你有帮助 生成随机数的一个可靠算法，高质量的均匀分布的随机函数
>
>

> 2009/8/11 四不象 <tabri...@gmail.com>

[四不象]

- - 这个方法代价也太大了

[Shuo Chen]

矛盾来了：假如你不记住所有已经生成的随机数，怎么准确知道新生成的数是否重复呢？

要想代价小，要么就用一些重复概率足够低的算法（比如生成UUID），问题是你能接受多高的重复概率？

换一个问题，你想生成多少位的随机数？
四不象 wrote:
> - - 这个方法代价也太大了

[陨落雕]

我最近几天也在想这个问题来着，有一个现实的意义就是极度简化版的url shorter，这样就不用用一个数据库来记录了，可以直接生成键值对。关键
问题是这个方法应该还是安全的，如果是线性同余只需要几个顺序的结果就可以算出来参数了。有这么一个生成方法之后就不用自增长的primary key
了，数据的安全性得到了保证（没办法通过用户id判断有多少注册用户之类的）。

觉得就是寻找一个给定初始条件的算法，在0~n次循环中不重不漏地产生0~n个数字，即使在给定任意足够长的产生的序列后第三方仍然无法（或者计算困难
的）在不知道初始条件的情况下预测下一个数字。

这个算法是不存在的。假设这个算法存在，那么在给定了前面产生的n-1个数字之后就可以准确预测下一个数字（因为产生的序列是不重不漏的）。

On Aug 11, 9:15 pm, Wenliang <wla...@gmail.com> wrote:
> 可以。但要满足一定条件，
> 比如a=5, b=3, c=0, x0 = 7, m=8
> x1 = (5*7 + 3) % 8 = 6
> x2 = (5*6 + 3) % 8 = 1
> x3 = (5*1 + 3) % 8 = 0
> x4 = (5*0 + 3) % 8 = 3
> x5 = (5*3 + 3) % 8 = 2
> x6 = (5*2 + 3) % 8 = 5
> x7 = (5*5 + 3) % 8 = 4
> 所以就随机选择满足条件的a, b, c, 初始值吧
> 四不象 wrote:英文看起来比较辛苦，线性同余可以保证生成随机数不重复？
>
> ----- Original Message -----
>
> From:Wenliang
>
> To:pon...@googlegroups.com
>
> Sent:Wednesday, August 12, 2009 11:05 AM
>
> Subject:[TL] Re: {询问}{算法}生成不重复未随机数的算法
>
>
>
> http://en.wikipedia.org/wiki/Linear_congruential_generator
> 四不象 wrote:好像这些随机数生成算法不能保证不重复
>
> ----- Original Message -----
>
> From:jrckkyy
>
> To:pon...@googlegroups.com
>
> Sent:Wednesday, August 12, 2009 12:44 AM
>
> Subject:[TL] Re: {询问}{算法}生成不重复未随机数的算法
>
>
>

> 前几天看了个类似的算法希望对你有帮助生成随机数的一个可靠算法，高质量的均匀分布的随机函数2009/8/11 四不象<tabri...@gmail.com>有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离 散度要比较好。

[Tiny fool]

我同意这点，如果你需要一个真随机，但是不重复的序列，那么你的做法应该是用一个真随机，可能重复的序列去掉重复的项来做。因为真随机和不重复这两个要求是冲突的，不重复则不可能是真随机。

假设要生成n个随机数，必须出现从1-n的每个数，那么第一个数生成的时候，这个算法是真随机的，那么随着数字的持续产生，这个随机算法的实际取值范围就递减，也就是实际相对于原有的取值范围来说，随机性越来越差。

2009/8/12 陨落雕 <geo...@gmail.com>

> 前几天看了个类似的算法希望对你有帮助生成随机数的一个可靠算法，高质量的均匀分布的随机函数2009/8/11 四不象<tabris17.cn@gmail.com>有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离 散度要比较好。

[四不象]

>这个算法是不存在的。假设这个算法存在，那么在给定了前面产生的n-1个数字之后就可以准确预测下一个数字（因为产生的序列是不重不漏的）。

 

伪随机数算法都是这样啊，只是初始种子不同而已，所以每次生成的序列不同罢了

[jrckkyy]

既然某种意义上的随机数可以产生了，即使他重复，可以通过建立一个不重复的大数组，然后下标通过随机机来进行一定的交换，就可以产生不重复的随机数了！

--
http://hi.baidu.com/jrckkyy

[四不象]

我就是想知道有没有一个简单的公式能够算出，而不需要一一判断

[qiaojie]

用线性同余法得到的伪随机序列就是不重复的，因为这个方法就是把每次的输出作为下一次的输入，如果出现重复的话，整个序列就开始循环了。当然，整个序列不可能无限长，最终还是会循环的，但是在整个序列范围内可以保证不重复。

[Tiny fool]

这个序列在周期内当然是不重复的，但是你把这个序列映射到你的取值范围内，就很难保证了吧？

比如，映射到整数0和1，两次就循环了。

2009/8/12 qiaojie <qia...@gmail.com>

[qiaojie]

映射到0和1，当然两次就循环了，那你还能怎么办呢？

 

根据线性同余公式

x = (a * x + b) % c

用c来控制序列的取值范围，选择合适的a，b系数让序列尽可能的长就可以满足楼主的需求了。

 

2009/8/12 Tiny fool <tiny...@gmail.com>

[realfun]

传说中的“洗牌算法”

http://blog.codingnow.com/2007/09/shuffle.html

好像The Art of Computer Programming关于随机哪一章提到，从n到1，依次让第i张和rand([1,i])交换就行了

哦，又搜了一下，在这里比较详细，有代码有真相：

http://en.wikipedia.org/wiki/Fisher–Yates_shuffle

1. Let A₁ := 1, A₂ := 2 and so on up to A_N := N, and let n := N.
2. Pick a random number k between 1 and n inclusive.
3. If k ≠ n, swap the values of A_k and A_n.
4. Decrease n by one.
5. Repeat from step 2 until n is less than 2.

传说这样生成的随机序列是unbiased

2009/8/12 qiaojie <qia...@gmail.com>

--
代码发芽网： http://fayaa.com/code/ （无需插件支持blog代码高亮，100+种语言，30+种高亮主题）
游戏发芽网： http://fayaa.com/youxi/ （华容道、数独等在线游戏及求解、图解）
我的Blog: 半瓶墨水(http://www.2maomao.com/blog)
Follow me @ http://twitter.com/realfun

[realfun]

一个简单的Python实现：

来自：http://code.activestate.com/recipes/360461/

import random

def shuffle(ary):
    a=len(ary)
    b=a-1
    for d in range(b,0,-1):
      e=random.randint(0,d)
      if e == d:
            continue
      ary[d],ary[e]=ary[e],ary[d]
    return ary

（其实python random库里面有个shuffle函数，但是不知道为什么其解释中提到了"permutation，似乎不是这么实现的，有机会就去查查看）

2009/8/12 realfun <rea...@gmail.com>

[qiaojie]

洗牌当然也是一种解法，但是需要占用很多的存储空间，如果需要一个很大范围的随机数序列，可能就存不下了。

 

 

2009/8/12 realfun <rea...@gmail.com>

[realfun]

奇怪为什么“洗牌占用很多的存储空间”，你是说随机数列大到超出物理内存？

2009/8/12 qiaojie <qia...@gmail.com>

[qiaojie]

如果范围要求是0~13亿呢，那就需要5G的内存空间，是不是不够了呢？

 

2009/8/12 realfun <rea...@gmail.com>

[Tiny fool]

同奇怪，楼主貌似正是在寻找洗牌算法，只是他说的不是这个词而已。

而不是说用洗牌算法来获取一个随机数列。

2009/8/12 qiaojie <qia...@gmail.com>

[qiaojie]

 

2009/8/12 Tiny fool <tiny...@gmail.com>

同奇怪，楼主貌似正是在寻找洗牌算法，只是他说的不是这个词而已。

而不是说用洗牌算法来获取一个随机数列。

 

 

莫要奇怪，请看楼主说：

 

2009/8/12 四不象 <tabris17.cn@gmail.com>
我就是想知道有没有一个简单的公式能够算出，而不需要一一判断

 

我想他的意思只是想通过一个轻量的方法得到一个不重复的随机序列而已。

 

[鋆邓]

线性同余算法在参数满足条件时，可保证周期与区间相同。也就是说，区间大小为N，那么N次随机内就不会重复。

参考：计算机程序设计与艺术（也就是Knuth那套书）第二卷

2009/8/12 qiaojie <qia...@gmail.com>

[四不象]

是的，呵呵，我表达得不太好

----- Original Message -----

From: qiaojie

To: pon...@googlegroups.com

Sent: Wednesday, August 12, 2009 10:51 PM

Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法

 

[wanng fenng]

你希望得到的序列服从什么样子的分布？均匀分布？泊松分布？正态？几何？指数？伽玛？二项？对于置信度要求有多高？

[四不象]

均匀分布，其实对分布没有要求，看上去随机就行

----- Original Message -----

From: wanng fenng

To: pon...@googlegroups.com

Sent: Thursday, August 13, 2009 10:55 AM

Subject: [TL] Re: {询问}{算法}生成不重复未随机数的算法

[Arthraim]

刚好最近博客写过类似的文章
http://arthraim.cn/post/2009/08/90.html

On Aug 11, 8:35 pm, rockeet <rock...@gmail.com> wrote:
> 有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。

> ----随机分布，不重复，是相互矛盾的需求
>
> 或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱
> ----这个问题，跟上一个问题并不等价，去看看 std::random_shuffle 的源码

[Arnkore .]

Wenbo Yang所言极是。
编程珠玑的开篇所讨论的问题便与此相关，其相关算发可解决你所提问题。

2009/8/11 rockeet <roc...@gmail.com>

有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。

----随机分布，不重复，是相互矛盾的需求

或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱
----这个问题，跟上一个问题并不等价，去看看 std::random_shuffle 的源码

On 8月11日, 下午6时23分, 四不象 <tabris17...@gmail.com> wrote:
> 有没有一种算法，可以得出一个随机数字序列，序列里的数字落在某个区间内，且不会重复，离散度要比较好。
>
> 或者换种说法，有没有一种快速算法，可以把一个顺序序列随机打乱

--
不以小智惊天下，但求大愚动世人。
http://blog.csdn.net/Arnkore

[宁静]

你可以先做一个顺序数列，然后一次去交换，可以做到不重复的，但是不可能是真随机。