還是回文整理一下好了
貼ar大的連結 洗牌法
正確來源是 良先生...啊是林先生...
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/AlgorithmGossip.htm
From Gossip@caterpillar
說明
---------
洗撲克牌的原理其實與亂數排列是相同的，都是將一組數字（例如1～N）打亂重新排列，
只不過洗撲克牌多了一個花色判斷的動作而已。
解法
---------
初學者通常會直接想到，隨機產生1～N的亂數並將之存入陣列中，後來產生的亂數存入陣
列前必須先檢查陣列中是否已有重複的數字，如果有這個數就不存入，再重新產生下一個
數，運氣不好的話，重複的次數就會很多，程式的執行速度就很慢了，這不是一個好方法
。
以1～52的亂數排列為例好了，可以將陣列先依序由1到52填入，然後使用一個迴圈走訪陣
列，並隨機產生1～52的亂數，將產生的亂數當作索引取出陣列值，並與目前陣列走訪到
的值相交換，如此就不用擔心亂數重複的問題了，陣列走訪完畢後，所有的數字也就重新
排列了。
至於如何判斷花色？這只是除法的問題而已，取商數判斷花色，取餘數判斷數字，您可以
直接看程式比較清楚。
關鍵 程式碼
========
final int N = 52;
int[] poker = new int[N + 1];
// 初始化陣列
for(int i = 1; i <= N; i++)
poker[i] = i;
// 洗牌
for(int i = 1; i <= N; i++) {
int j = (int) (Math.random() * N);
if(j == 0)
j = 1;
int tmp = poker[i];
poker[i] = poker[j];
poker[j] = tmp;
}
========
以上看出 如果原po想求是1~6隨機排列，一般人來說會想用random取六次不重複
但是處理重複會浪費效率
故即用洗牌方式，也就是迴圈來隨機swap，大約是O(N) 算線性時間
若原po先前還多加不必要的sort，則最好用的quick sort也會變 O(n*lgn)
備註tsya大的程式 如果我沒看錯的話 光是判斷重複就可能花 O(n*n)
而直到不重複停止 就像骰6顆骰子要出現一條龍那樣難，需要賭神才有辦法
※ 引述《tsya (tsya)》之銘言：
: 提供你 C 語言的 code 作參考
: 要寫 JAVA 版的 只要找到 API 就行了
: #include<stdio.h>
: #include<time.h>
: int duplicate(int r[6]){
: int i,j;
: for(i=0;i<6;i++)
: for(j=i+1;j<6;j++)
: if(r[i]==r[j])
: return 1;
: return 0;
: }
: int main(){
: int r[6]={0},i;
: srand(time(NULL));
: while(duplicate(r)==1)
: for(i=0;i<6;i++)
: r[i]=(rand()%6)+1;
: for(i=0;i<6;i++)
: printf("%d ",r[i]);
: printf("\n");
: return 0;
: }
: import java.util.Random;
: import java.util.Arrays;
: public class shuffle{
: static boolean duplicate(int a[]){
: int i,j;
: for(i=0;i<6;i++)
: for(j=i+1;j<6;j++)
: if(a[i]==a[j])
: return true;
: return false;
: }
: public static void main(String[] args){
: int[] a=new int[6];
: Random r=new Random();
: while(shuffle.duplicate(a)==true)
: for(int i=0;i<6;i++)
: a[i]=r.nextInt(6)+1;
: System.out.println(Arrays.toString(a));
: }
: }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.57.130
※ 編輯: teman 來自: 218.166.57.130 (09/04 09:58)
推
09/04 18:09, , 1F
09/04 18:09, 1F
討論串 (同標題文章)
完整討論串 (本文為第 7 之 7 篇)：