不重复的随机数生成问题！

第二个循环for(int j=0;j <100;j++)
改成for(int j=0;j <i;j++) 就可以了

你这个代码效率太低，看看我BLOG中洗牌和数独的代码会对你有很大的启发

Math.random()生成的随机数能保证不重复吗？

manbaum 的说法有一定道理，不过有一点不完整。
用“洗牌”方法最关键的一点，就是要抽出多少对数据交换多少次，简称（洗多少次牌？）。
理论上，至少洗 n/2 次才能洗到所有的牌。
但是，事实上，如果只洗 n/2 次，出现没洗完所有牌的几率很大当然，如果出现一张至几张牌还是在原来的位置，这种情况是绝对允许的。下面，我贴了个算法，得出三组数据比较两种取随机数的方法。
数据表示有多少个数据在原位置上取n/2对数据交换
  0    0    0    2    2    2    3    1    0    1
375  346  361  371  370  380  378  378  358  367取n对数据交换
  0    2    0    2    1    0    0    2    1    1
120  139  147  147  126  133  144  139  132  140取n*n对数据交换
  2    2    0    0    0    2    1    0    1    1
  0    1    0    0    3    2    1    0    0    1public class Main {

    public Main () {
        start ();
    }

    public static void main (String[] args) {
        new Main ();
    }

    private void start () {
        for (int i = 0; i < m; i++) {
            //
            for (int j = 0; j < n; j++) {
                iarr[j] = 0;
            }
            iarr_1[i][0] = g_1 ();
            //
            for (int j = 0; j < n; j++) {
                iarr[j] = j;
            }
            iarr_1[i][1] = g_2 ();
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < m; j++) {
                System.out.printf("%1$5s", iarr_1[j][i]);
            }
            System.out.println("");
        }
    }

    private int g_1 () {
        int j = 0;
        while(j < n-1) {
            int x = r.nextInt (n);
            if (iarr[x] == 0) {
                j++;
                iarr[x] = j;
            }
        }
        return check ();
    }

    private int g_2 () {
        for (int i = 0; i < n*n; i++) {
            int x = r.nextInt (n);
            int y = r.nextInt (n);
            {
                int c = iarr[x];
                iarr[x] = iarr[y];
                iarr[y] = c;
            }
        }
        return check ();
    }

    private int check () {
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (iarr[i] == i) {
                j++;
            }
        }
        return j;
    }

    private final int n = 1000;
    private int[] iarr = new int[n];
    private final int m = 10;
    private int[][] iarr_1 = new int[m][2];
    private java.util.Random r = new java.util.Random ();
}

第一排数据，是用 LS说的方法产生的 0～999 的随机数中，和原位置相等的个数
(比较了 10 次）
第二排使用交换的方法。也就是说，在0～999中，交换了（n/2 = 500)次。
结果总有 350 个数据左右在原位置。
这和用抽牌的原理取随机数的差距实在是太大了。
如果 n = 100 ,可能几十次就可以了。但是当 n 不确定时，你就不能确定，到底要换多少次
如果 n 为 1000，交换 1000 次，和第一种方法比较，就得以下数据。
0 2 0 2 1 0 0 2 1 1
120 139 147 147 126 133 144 139 132 140 数据相差之大，绝对不可取。
我测试的结果是，n = 1000,交换 n*n 次，得的结果才几乎和第一种方法相近。洗牌原理的缺点就在于，你是随机从 n 张牌种抽两张牌。
抽了 n 次可能有多张牌根本就没抽出来，
这和抽了两张牌交换位置，结果牌又到原位置上有本质区别
但是，如果抽的次数 > f(n) ，就一定可以得到接近于第一种方法的随机性
可，问题就是 f(n) 不知道是多少的。我测的结果是 f(n) = n*n
可能比这个大，也可能比这个小至于，LS 说第一种算法效率低。
我是不赞同的。上面贴的第一个函数的算法
随机生成0～999999 中的不重复数，只用了2秒（效率很高）
当然，随着 n 的增加，效率会越来越低。
不过，到那时候，也还可以在考虑算法的优化

谢谢大家的好意！
我的问题和洗牌是有区别的！
洗拍是已经确定了有固定的54张牌，再随机的产生这54张派的顺序！请注意，我所说的是从任意整数中（正整数和负整数）取出100个数，这100个数必须是1-100的不重复数字，所以我的这一百个数在每次取的是否首先要判断它是否在1到100之间，而不是一定确定它是1到100之间某一个数。
我代码的思路，我想大家都很明白，我就不在罗嗦！
我产生随机数后只是排序后输出，方便我查看！可总是有一个数字会重复，我总是找不出原因（我的代码好象也没什么问题），至于二楼朋友说的 for(int j=0;j <i;j++) 其实也就是循环次数少了，但结果一样！
希望各位再帮帮忙！

你重复的都是第一个打印出来的数字，只要将
temp = (int) (Math.random()*100+1);
j=0;
中的j=0;改成j=-1就可以了。

回答15楼：
我想如果是固定了1-100
那产生随机数当然就很容易了，
我把1-100存到一个集合里，随机get集合中的一个数字，再从集合中remove()，如此循环，保证不会有重复的数字！
这方法怎么样？回答16楼：
j=-1，那我再判断时不就越界限了吗？不过谢谢你的提醒！

回答15楼：
我想如果是固定了1-100
那产生随机数当然就很容易了，
我把1-100存到一个集合里，随机get集合中的一个数字，再从集合中remove()，如此循环，保证不会有重复的数字！
这方法怎么样？回答16楼：
j=-1，那我再判断时不就越界限了吗？而且我j=0同样可以判断第一个数是否重复啊！

我把1-100存到一个集合里，随机get集合中的一个数字，再从集合中remove()，如此循环，保证不会有重复的数字！
--------
想法没错。但是第一次你是生成0-99的下标，第二次是生成0-98的，因为去掉一个了，以此类推。一共要循环99次，因为最后一次就剩一个了，不用随机数了。
其实用这个办法的话，在原位也可以做，就是用交换的办法，是一样的。第一次生成0-99的下标，把这个下标的数和下标为99的数互换，第二次生成0-98的下标，把这个下标的数和下标为98的数互换，依次类推，也是需要99次循环。你的这个想法，我以前就考虑过，因为效率低，所以我没采用。用我说的办法，只要循环50-70次就足够了，满足绝大部分需要了，没必要99次。abc130314 提到有留在原位没有被交换的数，没有意义，这并不能完全代表乱的程度。除非你的随机数就那么凑巧，我觉得这种可能性不大。如果你说要完全避免，那是不可能的，你的任何算法都会出现随机数不“随机”，弄出规律来的情况。如果非要检测留在原位的数，那也不是数出有多少个留在原位的数的个数，而是看这些位置是不是总是不变，如果一直在变，那说明就洗牌够乱了，如果有大部分总是不变，那才能说明不够乱。

抽牌算法是有漏洞的。
1～n 张牌中，任选一张牌 K
因为抽牌是有放回的。
就以假设抽两张牌为例做 X 次实验，每次实验抽Y次牌那么，K 在每一此抽牌的过程中，都有(1/n)*(1/n) ＝ p(a) 的几率不被抽中即，做了 X 次实验，每次实验抽 Y 次牌
那么 K 总不被抽中的几率即为 p(a)^y ^x = p(A)p(A) ＝ p(a)^y^x ＝（(1/n)*(1/n）)^y ^x
严格意义来说，只要 n>1 ，p(A) 绝对不等于 0。
由此看来，这完全是天大的错误。
假设 K = 54,
那么 54 总以 p(A) 的概率不被抽中。
那么，意思就是说，你只拿了前 53 张牌来做随机实验
（因为 54 总不被抽到，所有 54 一直在牌的最下面）但是，从某种意义上来说，等于 0 是永远不可能的。
不过可以让 p(A)趋进于 0 ，这是完全可以的。
只要 p(A)趋进于 0 ，那么也就达到了随机的效果。
（但是，抽牌算法只是做一次实验，所以，就必须要求 Y 足够大，以至能是 p(A)趋进于 0 )
至于 Y 到底要多大，可以用高数求出来。
不过，如果你只是，以个人经验认为，100个随机数，抽个“七八十次”，那么这个数据是绝对不够严谨的。
虽然，可能， 100个随机数，也许求出来，Y<70 。
但是，对于 n个随机数，你就完全无法确定 Y。
如果你以 100个数随机的比例，认为 0.7n <= y <= 0.8n
那么，我可以说，你绝对是错的但是，如果用我上面类似的算法。就完全避免了这个问题。
因为，每次都是从剩下的牌中抽牌，所有就完全避免了某一个牌不会随机抽不到的问题。
可以说 p(A) 绝对等于 0。
虽然这种方法也有很小的几率会随机成 1,2,...54 的队列
但是，这完全和抽牌方法的完全没有抽到某张牌事件有本质的区别。不过，话说回来。
如果能求出一个函数 f(n) = y ，能让 p(A)趋进于 0。
那么，第二种方法也是可取的。复杂度，也会比第一种方法小得多。

更正：
上面 p(A) 算小了
p(A) ＝ p(a)^y^x ＝ ( (n-1)/n * (n-1)/n )^y ^x
不被抽中的几率应该有这么大

abc130314 你的说法本身就不对，我已经指出多次了。不能以某张牌位置没变来说明一副牌被打乱的程度。按你说的，54张，最后一张总的不变，那只要前53张牌被打乱了，那么这副牌就已经被打乱了。洗牌洗的是顺序，而不是具体位置上的牌变不变。另外，可以在洗牌后再模拟一次到两次切牌，这样就可以在某种程度上避免你说的问题，而算法效率不会降低。

这里有一个算法，可以保证随机性，而且复杂度是O（n）。
基本思想就是for each i:1-->n, swap（value[i], value[random(i, n)])
对于第i次随机选到的元素，有i个独立的随机事件，分别是i-1次未选中和1次选中
事件发生的概率=((n-1)/n）*((n-2)/(n-1))* …… *((n-i+1)/(n-i+2))*(1/(n-i+1)) = 1/n
所以每个元素的事件发生都是等概率的，而且时间复杂度线性。
这是算法导论上的一个例子import java.util.*;public class Randomize
{
public static final int MAX_SIZE = 100;
public static final int MAX_VALUE = 100;

public static void main(String [] args)
{
//Initialize the array
int [] value = new int[MAX_SIZE];
for(int i=0; i<value.length; i++)
{
value[i] = i+1;
}

//Randomize the Array
randomize(value);

    for(int i=0; i<value.length; i++)
    {
     if(i%10 == 0)
       System.out.println("");
     System.out.print(value[i]+"  ");
    }
  }


  public static void randomize(int [] value)
  {
   Random r = new Random();
   for(int i=0; i<value.length-1; i++)
   {
   int index = r.nextInt(MAX_VALUE-i)+i;
   int temp = value[i];
   value[i] = value[index];
   value[index] = temp;
   }
  }
}

manbaum 你说错了跳过
不能以某张牌位置没变来说明一副牌被打乱的程度。
来说。（个人认为，这个说法不全面。）从根本来看。第 n 张牌，被放在n位置的概率，一定是 p(a) ＝ 1/n
但是，你的方法产生的概率，p(a) ＝不被洗到的概率＋被洗到原位置的概率。不被洗到的概率＝ ((n-1)/n * (n-1)/n )^y
假设，被洗到原位置的概率＝ p(b) （ p(b) > 0 )
那么你的方法，产生的概率 p(a) ＝ ((n-1)/n * (n-1)/n )^y ＋ p(b)
因为，p(b) > 0
所以，可以100％肯定，
如果 ((n-1)/n * (n-1)/n )^y > 1/n，那么，洗牌打乱顺序就一定是错的。这样，你应该明白了吧。
洗牌就是一定要 y 足够大。
如果你不能确定 y 对于 n 来说，怎样才算足够大。
那么，你这个题目，就没法继续做了。

由数据就可看出
0 2 0 2 1 0 0 2 1 1
120 139 147 147 126 133 144 139 132 140 对于，n = 1000, y = 1000
所求得的概率 p(a) 和 1/n
这差别有多大

不能以某张牌位置没变来说明一副牌被打乱的程度。这句话有错误么？前面我提到，如果我做循环移动，那所有的牌都不在原位了，你认为这个是一个好的洗牌么？所以你的这个评判标准是错误的。拿100张牌举例，如果所有的牌都在原位，这个显然是可以确定这个洗牌太差了，和没洗一样；如果98张都在原位，你也可以说这个洗牌洗的不够乱；但是你能确定的说，有多少张或者超过多少张以上的牌在原位，就能说明这幅牌洗的不好么？所以你用这个作为标准，去算概率了什么的，都是没有意义的。你说“洗牌就是一定要 y 足够大”，我同意。实际上用y=n的算法（18、19、23楼所说），是可以解决问题的，用不着你说n*n次。但是我觉得y<n也是可以的，至少对于大部分应用，这个乱的程度已经够用了，比如100张牌里有30张牌没被洗到，是可以接受的，只要这30张牌不总是连续的。但我提供的算法里确实有个可能的问题，就是如果随机数生成的不好，导致固定位置的牌总是不被洗到，那就会有漏洞了。比如说，随机数序列生成的数里永远产生不了15，33，37，58，72等等这几个数。如果这样的数很多，那就会有问题。但这个可能性我觉得很小，这个是随机数发生器的故障了。还有一种情况用我的算法不work的就是，随机数发生在固定小区间(大区间就没问题了)里，比如第一洗，产生的数在[0，40]的区间里，大于40的都不产生；下一次洗，又产生[20,30]∪[50,80]的区间，这样就会有问题。但这种情况应该也属于随机数发生器的问题。

import java.util.*; public class Randomize
{
public static final int MAX_SIZE = 100;
public static final int MAX_VALUE = 100; public static void main(String [] args)
{
//Initialize the array
int [] value = new int[MAX_SIZE];
for(int i=0; i <value.length; i++)
{
value[i] = i+1;
} //Randomize the Array
randomize(value);     for(int i=0; i <value.length; i++)
    {
     if(i%10 == 0)
       System.out.println("");
     System.out.print(value[i]+"  ");
    }
  }


  public static void randomize(int [] value)
  {
   Random r = new Random();
   for(int i=0; i <value.length-1; i++)
   {
   int index = r.nextInt(MAX_VALUE);
   int temp = value[i];
   value[i] = value[index];
   value[index] = temp;
   }
  }
}

调试易

不重复的随机数生成问题！

解决方案 »