中國的彩票選號(hào)，例如36選7，從36個(gè)數(shù)字中隨機(jī)選取7個(gè)，這在算法上如何實(shí)現(xiàn)呢？
最簡單的想法就是，每次都從1～36隨機(jī)選取一個(gè)數(shù)，一共選7次，不就可以了嗎？
但這樣會(huì)有一個(gè)問題——重復(fù)。彩票選號(hào)是不能重復(fù)的，這也即是說如果你第一次選到的數(shù)是10，那么以后再從1～36中選數(shù)的時(shí)候，10就不能再選了。
有人可能會(huì)說了，這還不好辦，如果重復(fù)了就廢掉，重新再選一個(gè)唄。
這的確是一種解決方法，但是會(huì)有很大的問題，比如說5選4吧，前三個(gè)都已經(jīng)選好了是2，3，4，現(xiàn)在取第4個(gè)數(shù)，這種情況下，取到1和5的幾率要比取到2，3，4的幾率還要小，也就是說，最壞的情況下，有可能會(huì)取很多次2，3，4，扔掉很多次，才最終能取到1或5，完成4個(gè)隨機(jī)數(shù)字的選擇。顯然，這樣效率是有很大問題的。
下面就介紹一種算法：抽牌算法，來實(shí)現(xiàn)這種不允許重復(fù)的選號(hào)，同時(shí)不會(huì)出現(xiàn)這種效率上的問題。
[separator]
抽牌算法的核心思想如下：
以36選7為例
一副牌，一共36張，抽出其中一張牌，放到一邊，再從剩下的牌中抽出第二張，放到一邊……以此類推，直到抽完了7張牌為止。
很顯然，這樣抽牌是絕對(duì)不會(huì)重復(fù)的。而其核心就是
抽出的牌要放到一邊。
用算法如何實(shí)現(xiàn)呢？
其實(shí)很簡單，只要能模擬實(shí)現(xiàn)
把抽出的牌放到一邊這個(gè)概念就可以了，而模擬實(shí)現(xiàn)的方法是非常簡單的：把一個(gè)數(shù)組模擬成一個(gè)牌盒，用數(shù)組里存的數(shù)模擬牌，而
抽出的牌放到一邊的動(dòng)作，只需進(jìn)行一次
數(shù)組交換，把它放到數(shù)組的末尾即可。
以36選7為例
初始化數(shù)組，其結(jié)構(gòu)為[1,2.....35,36]
第一輪，從1～36序號(hào)中選取隨機(jī)序號(hào)，抽取到序號(hào)7， 把序號(hào)7和序號(hào)36的值交換，7放到數(shù)組的末尾，數(shù)組結(jié)構(gòu)變成[1...6,36,8......34,35,7]
第二輪，從1～35序號(hào)中選取隨機(jī)序號(hào)，抽取到7（這時(shí)位置7所存的數(shù)就是36了），把36和35交換，數(shù)組結(jié)構(gòu)就變成了[1..6,35,8...34,36,7]
第三輪，從1～34序號(hào)中選取隨機(jī)序號(hào)，抽取到5，把5和34交換，數(shù)組結(jié)構(gòu)變成了[1...4,34,6,35,8....5,36,7]
...
每一次，都把抽出的“牌”放到數(shù)組的最后，然后再抽牌時(shí)，就不抽最后那張牌，這樣就實(shí)現(xiàn)了
抽出的牌放到一邊這樣一個(gè)概念。
請(qǐng)看以下Java代碼：
- Java code
-
//獲得不重復(fù)的隨機(jī)數(shù)數(shù)組，取值范圍[min,max)，個(gè)數(shù)size
public static int[] getRandomIntWithoutReduplicate( int min, int max, int size )
{
int[] result = new int[size];//用于存儲(chǔ)結(jié)果的數(shù)組
int arraySize = max - min;//用于放"牌"的數(shù)組大小
int[] intArray = new int[arraySize];//用于放"牌"的數(shù)組
// 初始化"牌盒"，比如取值范圍是[3,10)則"牌盒"里放的"牌"就是3，4，5，6，7，8，9
for( int i = 0 ; i < intArray.length ; i++ )
{
intArray[i] = i + min;
}
// 獲取不重復(fù)的隨機(jī)數(shù)數(shù)組
for( int i = 0 ; i < size ; i++ )
{
int c = getRandomInt( min, max - i );//獲取到一個(gè)隨機(jī)數(shù)
int index = c - min;//這個(gè)隨機(jī)數(shù)在"牌盒"里的位置
swap( intArray, index, arraySize - 1 - i );//將這張"牌"放到"牌盒"的最后面
result[i] = intArray[ arraySize - 1 - i ];//把這張"牌"的值扔到存儲(chǔ)結(jié)果的數(shù)組里
}
return result;
}
//獲取隨機(jī)數(shù)，隨機(jī)數(shù)取值范圍為[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 )
{//交換數(shù)組arry, 序號(hào)x與序號(hào)y值的順序
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}