类彩票选号算法

Love The Way You Lie 2022-08-27 07:54 138阅读 0赞

中国的彩票选号，例如36选7，从36个数字中随机选取7个，这在算法上如何实现呢？ 最简单的想法就是，每次都从1～36随机选取一个数，一共选7次，不就可以了吗？ 但这样会有一个问题——重复。彩票选号是不能重复的，这也即是说如果你第一次选到的数是10，那么以后再从1～36中选数的时候，10就不能再选了。 有人可能会说了，这还不好办，如果重复了就废掉，重新再选一个呗。 这的确是一种解决方法，但是会有很大的问题，比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的。 下面就介绍一种算法：抽牌算法，来实现这种不允许重复的选号，同时不会出现这种效率上的问题。 \[separator\] 抽牌算法的核心思想如下： 以36选7为例 一副牌，一共36张，抽出其中一张牌，放到一边，再从剩下的牌中抽出第二张，放到一边……以此类推，直到抽完了7张牌为止。 很显然，这样抽牌是绝对不会重复的。而其核心就是抽出的牌要放到一边。 用算法如何实现呢？ 其实很简单，只要能模拟实现把抽出的牌放到一边这个概念就可以了，而模拟实现的方法是非常简单的：把一个数组模拟成一个牌盒，用数组里存的数模拟牌，而抽出的牌放到一边的动作，只需进行一次数组交换，把它放到数组的末尾即可。 以36选7为例 初始化数组，其结构为\[1,2.....35,36\] 第一轮，从1～36序号中选取随机序号，抽取到序号7， 把序号7和序号36的值交换，7放到数组的末尾，数组结构变成\[1...6,36,8......34,35,7\] 第二轮，从1～35序号中选取随机序号，抽取到7（这时位置7所存的数就是36了），把36和35交换，数组结构就变成了\[1..6,35,8...34,36,7\] 第三轮，从1～34序号中选取随机序号，抽取到5，把5和34交换，数组结构变成了\[1...4,34,6,35,8....5,36,7\] ... 每一次，都把抽出的“牌”放到数组的最后，然后再抽牌时，就不抽最后那张牌，这样就实现了抽出的牌放到一边这样一个概念。 请看以下Java代码：

//获得不重复的随机数数组，取值范围[min,max)，个数size  
    
        public static int[] getRandomIntWithoutReduplicate( int min, int max, int size )  
    
       {  
    
          int[] result = new int[size];//用于存储结果的数组  
    
           
    
         int arraySize = max - min;//用于放"牌"的数组大小  
    
         int[] intArray = new int[arraySize];//用于放"牌"的数组  
    
         // 初始化"牌盒"，比如取值范围是[3,10)则"牌盒"里放的"牌"就是3，4，5，6，7，8，9  
    
         for( int i = 0 ; i < intArray.length ; i++ )  
    
      {  
    
          intArray[i] = i + min;  
    
        }  
    
       // 获取不重复的随机数数组  
    
        for( int i = 0 ; i < size ; i++ )  
    
         {  
    
         int c = getRandomInt( min, max - i );//获取到一个随机数  
    
          int index = c - min;//这个随机数在"牌盒"里的位置  
    
           swap( intArray, index, arraySize - 1 - i );//将这张"牌"放到"牌盒"的最后面  
    
          result[i] = intArray[ arraySize - 1 - i ];//把这张"牌"的值扔到存储结果的数组里  
    
        }  
    
        return result;  
    
       }  
    
      //获取随机数，随机数取值范围为[min, max)  
    
      public static int getRandomInt( int min, int max )  
    
      {  
    
       // include min, exclude max  
    
        int result = min + new Double( Math.random() * ( max - min ) ).intValue();  
    
       
    
        return result;  
    
       }  
    
        
    
       private static void swap( int[] array, int x, int y )  
    
      {//交换数组arry, 序号x与序号y值的顺序  
    
        int temp = array[x];  
    
         array[x] = array[y];  
    
        array[y] = temp;  
    
      }

转帖注：如果采用集合来实现也可以做到，用数组效率上应该比集合要高一点点。