Java-如何生成0到N的 m（m<=N）个无重复随机数？

Question

如何生成0到N的 m（m<=N）个无重复随机数？

Answer 1

不知道这个行不行

 public void random(int m,int n){
System.out.println("random1");
Set<Integer> s = new HashSet<Integer>();
Random r = new Random();
while(s.size()< m){
int x = r.nextInt(n);
s.add(x);
}
System.out.println(s);
}

Answer 2

我认为的最好的方法

public class Test
{
/**
* @param args
* 方法七
* 先将所有空格平均分布在每个空位中，然后先正向拆解，再反向拆解，这样取得的数有极端值的概率很小
*/
public static void main(String args[])
{
long N=1000;
int m=10;
long []x=new long[m+1];
long s=N-m+1;
long t=s/(long)(m+1);
for(int i=0;i<m;i++)
{
x[i]=t;
s=s-t;
}
x[m]=s;
for(int i=0;i<x.length;i++)
//将数组x拆解，即抽取范围为x[i]的随机数，并放入x[i+1]中，依次类推
{
long g=(long)(Math.random()*(x[i]+1));
if(i==m)
{
x[m]-=g;
x[0]+=g;
}
else if(i==0)
{
x[0]-=g;
x[m]+=g;
}
else
{
x[i]-=g;
x[i+1]+=g;
}
}
for(int i=x.length-1;i>=0;i--)
{
long g=(long)(Math.random()*(x[i]+1));
if(i==0)
{
x[0]-=g;
x[m]+=g;
}
else if(i==0)
{
x[0]-=g;
x[m]+=g;
}
else
{
x[i]-=g;
x[i-1]+=g;
}
}
long z=0;
for(int j=0;j<m;j++)
{
z=z+x[j];
System.out.println(z);
z++;
}

}
}

方法一

/**
* @author Administrator
* 概率型算法，以确保取每个数的概率都为1N
*/
public class Test {
public static void main(String[] args) {
int N = 1000, m = 500, e = 0,j=0, k = 0,s=0;// 定义要取几个不重复的随机数m,N,游标
int[] x = new int[m];
while (true) {
// 出现该循环概率很小
boolean xn = false;
while (e <= (m*N))//因为概率为1/n，所以取m个数长度为m*N
{
if (k == m) {
xn = true;
break;
}
int g = (int) (Math.random() * (N+1));//抽取N个数中的一个
if (g == (N/2))//判断g是否为N/2,以图得 1/N的概率
{
x[k] = j;
k++;
}
e++;
j=(j==N+1)?0:j+1;
s++;
}
if (xn)
break;
else {
k = 0;
e = 0;
}
}
for (Integer i : x)
System.out.println("随机数:" + i);
System.out.println("执行了"+s+"次");
}

}

方法二

/**
* @author Administrator
* 方法二
*/
public class Test {
public static void main(String[] args) {
int N=1000,m=500,e=0,s=0;//定义要取几个不重复的随机数m,N,游标
int []x=new int[m];
while(e<m)
{
int g=(int) (Math.random()*(N+1));//随机数
boolean b=true;
for(int i=0;i<e;i++)
{
s++;
if(g==x[i]){b=false;break;}
}
if(b){x[e]=g;e++;}
}
//打印
for(int i=0;i<x.length;i++)
System.out.println(x[i]);
System.out.println("执行了"+s+"次");
}

}

方法三

public class Test
{
/**
* 方法三、
* 插空法的演变
* 虽然插空法比任何一种方法都要高效，但插空法会使所得的数呈现递减趋势，这就无法使取得的数分部均匀
* 由此演变出了另一种方案：
* 先取出，m个随机数，范围为N-m
* 如果他们的和大于N-m，那么削减一个空的的空格数，直到s<=N-m
* @param args
*/
public static void main(String args[])
{
int N=5000,m=10;
int []x=new int[m];
long s=0;
long xs=0;
for(int i=0;i<m;i++)
{
int x2=(int) (Math.random()*(N-m+1));
x[i]=x2;
s=s+x2;
xs++;
}
int h=0;
while(s>(N-m+1))
{
if(h==x.length)
h=0;
if(s>(N-m+1))
{
int t=(int)(Math.random()*x[h]);
x[h]=x[h]-t;
s-=t;
}
h++;
xs++;
}
for(int j=0,z=0;j<x.length;j++)
{
z=z+x[j]+1;
System.out.println(z);
}
System.out.println("执行了"+xs+"次");
}
}

方法四

public class Test
{
/**
* 方法四、
* 插空法
* @param args
*/
public static void main(String args[])
{
int N=5000,m=100;
int []x=new int[m];
long s=N-m+2;
long xs=0;
for(int i=0;i<m;i++)
{
int x2=(int) (Math.random()*s);
x[i]=x2;
s=s-x2;
xs++;
}
for(int j=0,z=0;j<x.length;j++)
{
z=z+x[j];
System.out.println(z);
z++;
}
System.out.println("执行了"+xs+"次");
}
}

方法五

public class Test
{
/**
* 插空法另一种演变，随机方法进行了改进，即先将x随机交换，然后再将已做好的随机数组再次拆解，分配
* @param args
*/
public static void main(String args[])
{
long N=(long) Math.pow(10, 15);
int m=300;
long []x=new long[m+1];
long s=N-m+1;
for(int i=0;i<m;i++)
{
long x2=(long) (Math.random()*s);
x[i]=x2;
s=s-x2;
}
x[m]=s;
for(int i=0;i<x.length;i++)
{
int ts=(int)(Math.random()*(x.length));
long g=0;
int gs=(int)(Math.random()*(x.length));
g=x[ts];
x[ts]=x[gs];
x[gs]=g;
}
for(int i=0;i<x.length;i++)
//将数组x拆解，即抽取范围为x[i]的随机数，并放入x[i+1]中，依次类推
{
long g=(long)(Math.random()*(x[i]+1));
if(i==m)
{
x[m]-=g;
x[0]+=g;
}
else
{
x[i]-=g;
x[i+1]+=g;
}
}
long z=0;
for(int j=0;j<m;j++)
{
z=z+x[j];
System.out.println(z);
z++;
}
}
}

方法六

import java.util.*;
public class Test
{
/**
* 方法六、
* 插空法的讲究概率的方式，虽然牺牲了一定的时间，但可以达到在m<(N2)的范围内，取出的数为不规则数列
* @param args
*/
public static void main(String args[])
{
long N=1000000;
int m=300;
long []x=new long[m+1];
long s=N-m+1;
for(int i=0;i<m;i++)
{
long x2=(long) (Math.random()*s);
x[i]=x2;
s=s-x2;
}
x[m]=s;
for(int i=0;i<(m+1)*(m+1);i++)
{
int ts=(int)(Math.random()*(x.length));
long g=(long)(Math.random()*(x[ts]));
int gs=(int)(Math.random()*(x.length));
if(x[gs]<(x[ts]*0.25))
{
x[ts]-=g;
x[gs]+=g;
}
else
{
g=x[ts];
x[ts]=x[gs];
x[gs]=g;
}
}
Arrays.sort(x);
for(int i=x.length-1;i>=0;i--)
//将数组x拆解，即抽取范围为x[i]的随机数，并放入x[i+1]中，依次类推
{
long g=(long)(Math.random()*(x[i]+1));
if(i==m)
{
x[m]-=g;
x[0]+=g;
}
else if(i==0)
{
x[0]-=g;
x[m]+=g;
}
else
{
x[i]-=g;
x[i+1]+=g;
}
}
long z=0;
for(int j=0;j<m;j++)
{
z=z+x[j];
System.out.println(z);
z++;
}
}
}

Answer 3

运用库函数

srand() // important!!!
rand()
可以生成随机数
然后用生成的数%n 就可以了

这是c里面的 我想java肯定也有库函数
如果库函数能做到的 就用库函数里的方法 这是我的做法
因为 如果你的随机算法如果更好那么 库函数设计者也太失败了

Answer 4

写在前面的：
其实我也不太清楚程序是怎么产生随机数的，不过我见过的大概是根据时间进行的一系列运算。
正文：
我认为可以采用这个办法，设立一个可以使用的数字链表，让一个指针变量在链表里循环，取数时读当前指针变量的数值。每取出一个数后进行一次链表的删除操作。

Answer 5

考虑用一个容器装 着要取范围内的随机数。然后随机一个数，在容器里取出这个数，然后继续随机。这样后期的效率应该会提高。

Answer 6

这个java中已经提供一个函数Collections.shuffle(list);

demo如下：

 List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<100;i++){
list.add(i);
}
Collections.shuffle(list);
for(int v:list){
System.out.println(v);
}

Answer 7

我的想法是这样的
1.先生成一个需要随机范围的数组，比如要随机n-m(n<m)之间的随机数，就生成一个初始长度为l = m-n,内容为从n依次递增到m的数组
2.随机一个0到l - 1的数字，以这个为下标去数组中寻找值，这个值为获取的随机值，然后把这个下标的值从数组中删去，数组长度-1
3.如果数组为空，则回到2，不然结束

这样就能生成n-m并且无重复的随机数序列

Answer 8

写一个C语言版本的 随机数生成器,切无重复.假设随机数在0~100以内;

 #include "iostream"
#include "time.h"
int main()
{

int n[101];
int m=0;
memset(n,-1,sizeof(int)*101);
srand((int)time(0));
while (m<50)
{
int count=rand()%100;
if (n[count]==-1)
n[count]=count;
m++;
}
for (int i=0;i<101;i++)
{
if (n[i]==-1)
continue;
printf("%d ",n[i]);
}
return 0;
}

Answer 9

说下我的思路，跟你一起探讨一下。

1.调用系统方法生成1个（0-N）的随机数i
2.再通过系统随机选择在（0-i）区间和（i-N）区间中的一个使用系统方法产生1个随机数
3.这样下去，直到产生M个随机数为止。

Answer 10

 import java.util.HashMap;

public class RandInt {

/**
* 返回cont个0-bigger之间的整数
*
* @param bigger 取值的最大值
* @param count 返回的数据长度
* @return 返回的数据
*/
public static int[] getRandArray(int bigger,int count) {
int[] retArray = new int[count];
HashMap<Integer,Boolean> map = new HashMap<Integer,Boolean>(count+1);

for (int i=0;i<count;i++) {
int t = (int) (Math.random()*bigger);
while(map.containsKey(t)) {
t = (int) (Math.random()*bigger);
}
map.put(t, true);
retArray[i] = t;
}
return retArray;
}

/**
* @param args
*/
public static void main(String[] args) {
int[] a = getRandArray(100,10);
for(int i=0,len=a.length;i<len;i++) {
System.out.print(a[i] + " ");
}
}
}

没有用任何算法。

Answer 11

直接上O(m)的算法

 int[] r = new int[m];
Dictionary<int, int> replaceTable = new Dictionary<int, int>();
for(int i = 0; i < m; i++)
{
int g = (int)(Math.random() * (n - i));
int v;
if(replaceTable.TryGetValue(g, out v))
{
r[i] = v;
}
else
{
r[i] = g;
}
if(replaceTable.TryGetValue(n - i - 1, out v))
{
replaceTable[g] = v;
}
else
{
replaceTable[g] = n - i - 1;
}
}

算法的原理很简单：
假想有一列N个元素排在你面前，你随便从中间抽走一个。然后就留下了一个空在这里。有空在这里下次抽到了怎么办？要把空填上，于是你把整列的最后一个元素拿起来填到了空位上。下次就是从N-1个元素里取一个。
因为N可能很大，所以用一个HashTable替代数组。如果replaceTable[i]不存在，就认为值为i。剩下的代码就顺理成章了。