彩票选号后的数学——抽牌算法的实现

很简单的一个小算法，抛砖引玉了。

中国的彩票选号，例如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;
  }

确实如楼主所言，有这样的问题存在。
之前我也做过一个类似彩票选号的程序，在一定范围内随机选择数字，不能重复。当时也想到过会有这样的问题存在，可能不会非常的极端，不会影响到实际的应用。

当时偷懒，就没有去实现楼主说说的算法。

顺便贴一下当时偷懒的程序，做个反面教材：

 /**
 *随机生成数值。nums表示个数，size表示范围即最大数。
 */
 static int[] getNums(int nums,int size){
  int[] arr=new int[nums];
  Random r=new Random();
  for (int i=0;i<nums;i++ ){
   //生成范围内的随机数。
   arr[i]=r.nextInt(size)+1;
   //剔除重复的数值。
   for (int j=0;j<i;j++){
    if (arr[j]==arr[i]){
     i--;
     break;
    }
   }
  }
  //排序。从小到大排列。
  Arrays.sort(arr);
  return arr;
 }

以前做过一个抽奖活动，当时采用下面的做法：

		List<Integer> userList = lotteryTaskDao.getUsersByDay(day);
		long size = userList.size();
		StringBuffer userIds = new StringBuffer();		
		if (size > prizeCount) {
			for (int i = 0; i < prizeCount; i++) {
				int prize = (int) (Math.random() * size);				
				userIds.append(String.valueOf(userList.get(prize))).append(",");

				size--;
				userList.remove(prize);
			}
		} else {
			for (int i = 0; i < size; i++) {
				userIds.append(String.valueOf(userList.get(i))).append(",");
			}	
		}

userList 是参与抽奖的用户ID集合，prizeCount需要抽出中奖的用户数。

当时忘记怎么做了
只记得有个linkedlist
每次在搜有list的size去随即
得到的那个remove放到数组里面

swap就好比数组里面的get remove

不明白楼主上面的话，查看API帮助文档，用随机返回的值都是均匀分布的，为什么楼主说取2，3，4，的机会会比1，5多呢？

写了一个小程序测试：

public class RandomTest {

    public static void main(String[] args) {
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	int ramdonValue;
	;
	for (int i = 0; i < 10000000; i++) {
	    ramdonValue = (int) (Math.random() * 10);
	    if (map.get(ramdonValue) != null) {
		map.put(ramdonValue, map.get(ramdonValue) + 1);
	    } else {
		map.put(ramdonValue, ramdonValue);
	    }
	}

	for (Integer key : map.keySet()) {
	    System.out.println(key + ": " + map.get(key));
	}
    }

}

执行了10000000次，获得的1-10的结果离平均值在本机的N次运行中发觉不会大于士800次……下面的是一个参考结果：
0: 1000477
1: 1000093
2: 1000188
3: 1000643
4: 999796
5: 1000063
6: 998529
7: 998709
8: 1000817
9: 1000720

是不是楼主的说法有误呢？

我的意思是说，去到2，3，4的总的几率是3/5，取到1，5的几率是2/5，自然是取到2，3，4的机会比取到1，5的机会要大一些了。

扩展开去，比如100选99，假设前98个数已经选好了，现在选第99个数，那么，如果按照1～100随机取值的方法去选第99个数，选到前98个数字的机率要远高于没选到的那2个数字，机率分别是0.98和0.02，不知我这样解释还算明白？

嗯，终于明白，受教了，谢谢。

也可以借助Java内部实现来实现这个功能

List<Integer> box = new ArrayList<Integer>();
for(int i=0; i < 36; ++i){
    box.add(i+1);
}

Collections.shuffle(box);

return box.subList(0,4);

代码是示意性的,借助Collections内置的shuffle(洗牌)之后,取前五个就可以了

明显站不住脚，5选4等价于5选1，根本用不着多此一举。

用ArrayList是不是更方便一点，直接可以remove被选中元素。