[心得] 亂數不重複的方法

[csihcs (非天夜翔)]

示範內容：
　　以 C++ code 達成一付樸克牌(張數deckSize)取 getSize 張牌。
    假設前提 deckSize >= getSize > 0，
    在此不做這項檢查。

方法一：驗證法，新手常想到要用的方法
  int* getCards(int deckSize,int getSize) {
　  srand(time(NULL));
　  int *cards = new int[getSize];
　  // 取第一張牌
　  cards[0] = rand()%deckSize + 1;
　  for(int i = 1 ,j,g; i < getSize ; ) {
　    // 取牌
　    g = rand()%deckSize() + 1;
　    // 檢查手牌是否有相同的牌
　    for(j = 0 ; j < i ; ++j) {
　      if(g == cards[j])
　        break;
　    }
　    // 沒有抽過則放入手牌
　    if(j==i) {
　      cards[i] = g;
　      ++i;
　    }
　  }
　  return cards;
　}

  想法：[以時間節省空間]
      取一張牌，檢驗是否前面曾經取過，
      有則重新再一次。
  優點：
      較為直觀，較省記憶體空間。
　缺點：
      當 getSize 接近 deckSize 時，
      檢查次數越多且會越頻繁，因為相同牌的機率越來越大。
      甚至當 getSize == deckSize 這個情況最為嚴重。
  適用時機：
      getSize 與 deckSize 相比很小的時候。
      比較方法是 getSize / deckSize 越接近 0 越適合。
      狀況：記憶體空間小的時候。

方法二：洗牌法，版上及Google查到常用的方法
  int* getCards(int deckSize,int getSize,int washtime) {
　  srand(time(NULL));
　  int *cards = new int[getSize];
　  int *deck = new int[deckSize];
　  // 建立牌堆
　  for(int i = 0 ; i < deckSize ; ++i ) {
　    deck[i] = i + 1;
　  }
　  // 洗牌
　  for(int i = 0,temp,j,k; i < washtime ; ++i) {
　    j = rand()%deckSize;
　    k = rand()%deckSize;
　    temp = deck[j];
　    deck[j] = deck[k];
　    deck[k] = temp;
　  }
　  // 取前 getSize 張牌作為手牌
　  for(int i = 0 ; i < getSize ; ++i) {
　    cards[i] = deck[i];
　  }
　  delete [] deck;
　  return cards;
　}

  想法：[以空間換取時間]
      建立一付牌的 index，
      根據給定的洗牌次數，隨機將兩張牌互換，
      最後，取前 getSize 張牌就是所需的牌組。
  優點：
      避開檢查所取的牌與前面取的牌是否重複。
      所需時間穩定。
　缺點：
　　　需要較多記憶體空間，以及要洗牌的時間。
  適用時機：
      getSize 與 deckSize 相比很接近的時候。
      比較方法是 getSize / deckSize 越接近 1 越適合。
      需求：有足夠的記憶體空間。
  附註：
      洗牌的 code 有人建議用下面的方案取代
　　　for(int i = 0,j,temp ; i < deckSize ; ++i) {
　      j = rand()%deckSize;
　      temp = deck[j];
　      deck[j] = deck[i];
　      deck[i] = temp;
　    }
      這樣可以保證牌堆中每一張牌都被換過一次。

方法三：抽牌法
　int* getCards(int deckSize, int getSize) {
　  srand(time(NULL));
　  int *cards = new int[getSize];
　  int *deck = new int[deckSize];
　  // 建立牌堆
　  for(int i = 0 ; i < deckSize ; ++i) {
　    deck[i] = i + 1;
　  }
　  // 抽牌放入手牌，並將牌堆最後一張放到抽出的位置
　  for(int i = 0,j ; i < getSize ; ++i) {
　    j = rand()%deckSize;
　    cards[i] = deck[j];
　    deck[j] = deck[--deckSize];
　  }
　  delete [] deck;
　  return cards;
　}

  想法：[以空間換取時間]
　　　抽牌後，將牌堆最後一牌取代抽走的牌，牌堆數量減少，
　優點：
　　　相較於洗牌法少去洗牌的時間。
      如果 deck 這個 array 能夠維護的好，
      可以將他修成能夠重複使用的方式，
      如此會另有洗牌的效果存在。
　缺點：
　　　需要較多的記憶體空間。
　適用時機：
　　　getSize 與 deckSize 相比很接近的時候。
      比較方法是 getSize / deckSize 越接近 1 越適合。
      需求：有足夠的記憶體空間。

方法四：機率法［眠月大大提供］
    int* getCards(int deckSize,int getSize) {
        srand(time(NULL));
        int *cards = new int[getSise];
        for(int i = 0,got = 0 ; i < deckSize ; ++i) {
          if( rand() % (deckSize-i) < (getSize-got) ) {
            cards[got] = i + 1;
            ++got;
          }
        }
        return cards;
    }
    想法：
        將牌堆跑過一次，
        利用機率的方式取牌，這次取牌則機率變低，反之變高。
    優點：
        兼顧時間與空間，
        空間複雜度為Ｏ(1)，時間複雜度Ｏ(deckSize)
    缺點：
    　　getSize / deckSize 越接近 ０ 所需時間越長。
    適用時機：
      　getSize 與 deckSize 相比很接近的時候。
　      比較方法是 getSize / deckSize 越接近 1 越適合。

想法五：ＳＴＬ［tinlans大大提供］
    #include <iostream>
    #include <algorithm>
    #include <functional>
    #include <vector>
    #include <ctime>
    #include <cstdlib>
    using namespace std;
    // random generator function:
    ptrdiff_t myrandom (ptrdiff_t i) { return rand()%i;}
    // pointer object to it:
    ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
    int* getCards(int deckSize,int getSize) {
      srand(time(NULL)));
      vector<int> myvector;
      vector<int>::iterator it;
      int *cards = new int[getSize];
      // set some values:
      for (int i=1; i<=deckSize; ++i)
        myvector.push_back(i);
      // using built-in random generator:
      random_shuffle ( myvector.begin(), myvector.end() );
      // using myrandom:
      random_shuffle ( myvector.begin(), myvector.end(), p_myrandom);
      // get content:
      for (it=myvector.begin(); it!=myvector.end(); ++it) {
         if( getSize > 0 )
           cards[--getSize] = *it;
      }
      return cards;
    }
    想法：
        明明就已經有人做好輪子了，
        不用還在那邊自己造輪子。
    優點：
        不用自己造輪子。
    附註：
        code 參考自
          http://www.cplusplus.com/reference/algorithm/random_shuffle/

以上是我目前知道的幾種方法，請板上的大大多多指教。m(_@_)m

最後的 P.S. 適用時機提到的 getSize / deckSize 是浮點數運算喔。

別跟我說你得到的值不是 0 就是 1，那我就救不了了。［昏倒］

謝謝看完。現在不敢騙Ｐ幣了啦！！Ｑ。Ｑ＂，版主饒了我。［飛奔逃走］

--
渴望飛翔在自由的風中，
期望逃離這拘束的現實，
一切都讓他隨著風而去，
獨自躲在黑暗的空氣中，
舔舐被狠狠撕裂的傷口。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.9.2
→ ykjiang:你漏掉一種兼顧時間及空間的方法
→ ykjiang:時空兼顧法要機率夠好才看得懂
→ csihcs:請問可以提供一下嗎???以前沒有用到其他的方法Q.Q" m(_@_)m
→ BillSky:抽牌法和只用一個陣列
→ nowar100:我也只是在公就事論事 上次那篇真的太誇張
→ tinlans:std::random_shuffle() 洗一遍不就好了。
→ csihcs:對齁~都忘記有STL還要自己造輪子 ~~~ faint
※ 編輯: csihcs          來自: 211.74.9.2           (02/13 12:01)