寻找将1~N的整数随机排列的高效方法-图灵社区

寻找将1~N的整数随机排列的高效方法

lt 发表于 2016-06-23 12:49 2748 阅读

我想到的是：先把数组按照顺序初始化，然后随机从1~N-1取一个位置，把这个位置的值与放在N位置的值交换，然后再随机从1~N-2取一个，与放在N-1位置的值交换...直到只剩一个，放在那里不动。最终结果正好是倒序的每次取出的随机数,但有的数可能会被多次取到。

#include <stdio.h>
#define N 14
#define P {int i;for(i=1;i<=N;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[N+1];
int temp=0;
int j=0;
for(i=1;i<=N;i++) a[i]=i;
P
for(i=1;i<N;i++) 
{
j=rand()%(N-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
P
}
return 1;
}

比如：初始化 1 2 3 4 5
1. 找到1~4的随机数3，序列变为1 2 [5] 4 [3]
2. 找到1~3的随机数2，序列变为1 [4] 5 [2] 3
3. 找到1~2的随机数2，序列变为1 [5] [4] 2 3
其中4这个数就多次被取到。

本文仅用于学习和交流目的，不代表图灵社区观点。非商业转载请注明作译者、出处，并保留本文的原始链接。

4推荐收藏感谢

不会正文贴代码,加了4个空格还是合成一堆
#include <stdio.h>
#define P {int i;for(i=1;i<=10;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[11];
int temp=0;
int j=0;
for(i=1;i<=10;i++) a[i]=i;
P
for(i=1;i<=10;i++)
{
j=rand()%9+1;
temp=a[j];
a[j]=a[10-i+1];
a[10-i+1]=temp;
P
}
return 1;
}

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 10 7 8 9 6
1 2 3 4 5 10 7 8 9 6
1 2 3 4 5 10 7 8 9 6
1 2 3 4 7 10 5 8 9 6
1 2 3 4 7 9 5 8 10 6
1 7 3 4 2 9 5 8 10 6
1 7 3 4 2 9 5 8 10 6
3 7 1 4 2 9 5 8 10 6
3 8 1 4 2 9 5 7 10 6
1 8 3 4 2 9 5 7 10 6

lt 发表于 2016-06-23 13:19:52

推荐
- 博客园的评论可以对代码进行语法高亮，这点值得图灵社区学习。
  
  黄志斌发表于 2016-06-23 14:59:20
- 例如：http://www.cnblogs.com/skyivben/archive/2008/07/25/1251697.html#1802738
  
  黄志斌发表于 2016-06-23 15:00:54
- 如果要在评论中贴代码，可以使用全角的空格，就不会挤成一堆了。
  
  黄志斌发表于 2016-06-23 15:02:30
- 例如：http://www.ituring.com.cn/article/216999 的一些评论。
  
  黄志斌发表于 2016-06-23 15:04:41
- 谢谢，我原来就没加空格：）但评论的回复总是挤成一堆
  
  lt 发表于 2016-06-23 15:06:55
- 在评论中使用全角的空格就不会挤成一堆。
  
  黄志斌发表于 2016-06-23 15:13:00
- 您误解了，"评论"不会挤成一堆，是因为可以换行。"评论的回复"会挤成一堆，是因为不可以换行。比如下面的＂
  　我是一个全角空格
  我要换行，
  　　结果还是挤成一堆＂
  
  lt 发表于 2016-06-23 15:21:15
- 嗯，的确如此。是我误解了。
  
  黄志斌发表于 2016-06-23 15:26:19
前一个代码写错了,重写
#include <stdio.h>
#define P {int i;for(i=1;i<=10;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[11];
int temp=0;
int j=0;
for(i=1;i<=10;i++) a[i]=i;
P
for(i=1;i<10;i++)
{
j=rand()%(11-i)+1;
temp=a[j];
a[j]=a[10-i+1];
a[10-i+1]=temp;
P
}
return 1;
}

1 2 3 4 5 6 7 8 9 10
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 8 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 4 3 5 8 6 7 9 2
4 10 1 3 5 8 6 7 9 2
10 4 1 3 5 8 6 7 9 2

lt 发表于 2016-06-23 13:24:30

推荐
tcc的rand和vc的居然一模一样
D:\>tcc\tcc -run sj.c
1 2 3 4 5 6 7 8 9 10
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 8 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 4 3 5 8 6 7 9 2
4 10 1 3 5 8 6 7 9 2
10 4 1 3 5 8 6 7 9 2

lt 发表于 2016-06-23 13:27:06

推荐
把数组长度变成变数，并改了一个小错误
#include <stdio.h>
#define N 14
#define P {int i;for(i=1;i<=N;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[N+1];
int temp=0;
int j=0;
for(i=1;i<=N;i++) a[i]=i;
P
for(i=1;i<N;i++)
{
j=rand()%(N-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
P
}
return 1;
}

lt 发表于 2016-06-23 13:33:52

推荐
C 语言的伪随机数生成函数需要初始化，例如：
srand(time(NULL));
否则每次生成的伪随机数都是一样的。

空军发表于 2016-06-23 14:24:50

推荐
- 了解,但不同编译器结果相同,是都调用同样的操作系统函数生成,还是算法都一样?
  
  lt 发表于 2016-06-23 14:37:02
- 我猜是算法相同。
  另，C 语言的 main() 函数用 reutrn 0; 表示正确返回。
  
  空军发表于 2016-06-23 14:40:08
- 谢谢指教。
  
  lt 发表于 2016-06-23 14:44:32
- 随机数生成的算法，在 Linux 操作系统中，是使用 The GNU C Library (glibc) ，不同的 C 编译器都用它。
  
  黄志斌发表于 2016-06-23 15:11:59
- http://www.gnu.org/software/libc/index.html
  
  黄志斌发表于 2016-06-23 15:12:16
这个方法调用N-1次随机函数，好像次数不能再减了。

lt 发表于 2016-06-23 14:43:52

推荐
- 对小的 N 可以减啊。
  见我的下一条评论（因为评论的回复不能换行，会挤到一行，所以另写一条评论。）
  
  空军发表于 2016-06-23 14:47:57
- 最后一步不做交换是否影响随机性?感觉是不影响.因为本身只有一个位置，交换也是直接交换
  
  lt 发表于 2016-06-24 08:44:15
1~N 的排列共有 N! 个，例如 N = 3 的情形：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

随机产生一个 1~N! 范围的随机数，
比如生成的随机数是 4，
就输出上述第 4 个排列：2 3 1。

空军发表于 2016-06-23 14:51:31

推荐
- 学习了，这算查表法吧，就看生成表和随机函数哪个开销大
  
  lt 发表于 2016-06-23 14:53:45
- 怎么验证一个序列的随机性？
  比如321-465-897就不随机，数据扎堆了
  
  lt 发表于 2016-06-23 16:32:20
- 自己找到了，<计算机程序设计艺术> 3.3 统计检验
  
  lt 发表于 2016-06-23 16:36:16
- 我想，任何一个序列都是随机的，比如 123456789 也可以认为是随机序列。
  
  空军发表于 2016-06-23 16:36:21
- 是我没表达清楚,我是说如果有个算法每次出来的都是xxx-yyy-zzz这种模式，其中相同的字母除以3取整后相同，那一定不随机
  
  lt 发表于 2016-06-23 17:03:28
- 《计算机程序设计艺术卷2：半数值算法（第3版）》第 110 页第 1行：
  如果 t 很小，则我们可以通过产生 1 到 t! 之间的随机整数，快速得到一个随机排列。
  
  黄志斌发表于 2017-09-15 08:56:51
- @黄志斌写个科普文章吧
  
  lt 发表于 2017-09-15 11:00:22
正文中的：
然后随机从1~N-1取一个位置
应改为：
然后随机从1~N取一个位置
以此类推。见：图灵社区：生成随机排列
http://www.ituring.com.cn/article/217419

黄志斌发表于 2016-06-25 14:49:12

推荐
- 谢谢,学习了
  
  lt 发表于 2016-06-25 15:14:55
#include <stdio.h>
#define N 100
#define P {int i;for(i=1;i<=N;i++)printf("%d ",a[i]);printf("\n");}
int fill(int a[])
{
for(int i=1;i<=N;i++) a[i]=i;
return 0;
}

int m1(int a[])
{
int i=0;
int temp=0;
int j=0;
for(i=1;i<N;i++)
{
j=rand()%(N+1-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
}
return 0;
}

int m2(int a[])
{
int i=0;
int temp=0;
int j=0;
for(i=1;i<N;i+=2)
{
j=rand()%(N+1-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
j=N+1-i-j; //仿照顺序查找的算法Q'，在一次循环中处理2个位置
if(j>0)
{
temp=a[j];
a[j]=a[N-i+1-1];
a[N-i+1-1]=temp;
}
}
return 0;
}

int main()
{
int a[N+1];

for(int k=0;k<1000000;k++)
{
fill(a);
//测试第1种方法
//m1(a);
m2(a); //测试第2种方法
}

return 0;
}
//运行测试
方法1:
D:\lt>\timer tcc\tcc -run rp.c
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

Kernel Time = 0.078 = 2%
User Time = 3.494 = 97%
Process Time = 3.572 = 99%
Global Time = 3.597 = 100%
方法2:
D:\lt>\timer tcc\tcc -run rp.c
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

Kernel Time = 0.078 = 3%
User Time = 2.449 = 95%
Process Time = 2.527 = 98%
Global Time = 2.554 = 100%

lt 发表于 2016-06-26 12:59:43

推荐
如果先生成一堆大随机数拼成长串，然后每次用一小段如何

lt 发表于 2016-06-28 20:05:57

推荐

lt
- 关注
- 短消息

寻找将1~N的整数随机排列的高效方法

lt

相关图书

C# 4.0图解教程