Spirit's Home

    中国的彩票选号如：22选5、七乐彩（30选7）、双色球等这类需要选择不重复的号码。像30选7从30个数字中随机选取7个，这在算法上如何实现呢？

最简单的想法就是，每次都从1～30随机选取一个数，一共选7次，不就可以了吗？
但这样会有一个问题——重复。彩票选号是不能重复的，这也即是说如果你第一次选到的数是10，那么以后再从1～30中选数的时候，10就不能再选了。 有人可能会说了，这还不好办，如果重复了就废掉，重新再选一个呗。 这的确是一种解决方法，但是会有很大的问题，比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的。最重要的是和真实的开奖有很大的差别，并不能真正模拟开奖。

推荐抽牌算法来实现这种不允许重复的选号，不会出现这种效率上的问题，并且类似真实福利彩票的开奖环境。

抽牌算法的核心思想如下：
以30选7为例
一副牌，一共30张，抽出其中一张牌，放到一边，再从剩下的牌中抽出第二张，放到一边……以此类推，直到抽完了7张牌为止。
很显然，这样抽牌是绝对不会重复的。而其核心就是抽出的牌要放到一边。

用算法如何实现呢？
其实很简单，只要能模拟实现把抽出的牌放到一边这个概念就可以了，而模拟实现的方法是非常简单的：把一个数组模拟成一个牌盒，用数组里存的数模拟牌，而抽出的牌放到一边的动作，只需进行一次数组交换，把它放到数组的末尾即可。

以30选7为例
初始化数组，其结构为[1,2.....29,30]
第一轮，从1～30序号中选取随机序号，抽取到序号7，把序号7和序号30的值交换，7放到数组的末尾，数组结构变成[1...6,30,8......28,29,7]
第二轮，从1～29序号中选取随机序号，抽取到7（这时位置7所存的数就是30了），把30和29交换，数组结构就变成了[1..6,29,8...28,30,7]
第三轮，从1～28序号中选取随机序号，抽取到5，把5和28交换，数组结构变成了[1...4,28,6,29,8....5,30,7] ...
每一次，都把抽出的“牌”放到数组的最后，然后再抽牌时，就不抽最后那张牌，这样就实现了抽出的牌放到一边的概念，从而模拟了真实的开奖过程。
附一C++代码：
#include <iostream>
#include <ctime>
using namespace std;
int a[30];
int main()
{
 int i,j;
 int temp;
 for(i=0;i<30;i++)
  a[i]=i+1;
 srand((unsigned int)time(NULL));
 for(i=30;i>23;i--)
 {
  j=rand()%i;
  temp=a[j];
  a[j]=a[i-1];
  a[i-1]=temp;
 }
 for(i=29;i>23;i--)
 {
  cout<<a[i]<<" ";
 }
 cout<<endl;
 return 0;
}