2014年2月19日 星期三

Shuffling a deck of cards

Implement a function that can shuffle a deck of cards, and each of all the permutations (52!) is equally likely to happen, i.e., a perfect shuffle.

實作一個洗牌程式，使得 52! 種可能的撲克牌順序出現的機率是相同的

作法一：

  1. 時間: 當n變大, 未知久
首先假設4種花色，各13張牌，依照一定順序對應到數字1~52，利用隨機產生的數 (1~52) 來決定下一張出現的牌為何者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

void shuffle( const int n ){
    vector<bool> cardVec(n, false);
    int done = 0;
    srand( time(NULL) );

    int nextPickedCard;
    while( done != n ){
        nextPickedCard = rand( ) % n;
        if( !cardVec[nextPickedCard] ){
            cardVec[nextPickedCard] = true;
            done++;
            cout << nextPickedCard << endl;
        }

    }
}

int main( ){
    cout << "The number you want to shuffle: ";

    int n;
    cin >> n;
    shuffle(n);
}

作法二：

  1. O(n^2)
第一種作法的問題在，會不斷的挑到已經洗好的牌，時間會在n越大時，大幅度的上升
解決此問題，假設扣去取出的牌，剩餘m張牌，可以利用隨機產生的1~m個數字來表示，取出剩餘的第幾張牌，藉此以避免重複取出相同的牌

e.g. 1 2 3 4 5 6
1-6隨機取5 則1 2 3 4 5 6 , 取出剩餘中第5個人, 5    -> 5
1-5隨機取3 則1 2 3 4 5 6 , 取出剩餘中第3個人, 3    -> 5 3
1-4隨機取3 則1 2 3 4 5 6 , 取出剩餘中第3個人, 4    -> 5 3 4
1-3隨機取1 則1 2 3 4 5 6 , 取出剩餘中第1個人, 1    -> 5 3 4 1
1-2隨機取1 則1 2 3 4 5 6 , 取出剩餘中第1個人, 2    -> 5 3 4 1 2
1-1隨機取1 則1 2 3 4 5 6 , 取出剩餘中第1個人, 6    -> 5 3 4 1 2 6

此方法稱作Fisher–Yates shuffle

C++ 實作:

1. vector, 必須每次erase已經選出的人, relocate剩下的人的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>    // for "find"
using namespace std;

void shuffle( const int n ){
    // initialize a check vector
    vector<int> cardVec;
    for( int i = 0 ; i < n ; i++ )
        cardVec.push_back(i);


    srand( time(NULL) );
    int leftCardNum = n;
    int nextPickedCard;
    vector<int>::iterator numberErase;// temp pointer
    while( leftCardNum != 0 ){
        // pick a number m to choose the card at this location m
        nextPickedCard = rand( ) % leftCardNum;
        int &picked = cardVec[nextPickedCard];
        cout << picked << " ";
        numberErase = find( cardVec.begin(), cardVec.end(), picked );
        cardVec.erase(numberErase);

        leftCardNum--;
    }
}

int main( ){
    cout << "The number you want to shuffle: ";

    int n;
    cin >> n;
    shuffle(n);
}
Note: 
line22 可以直接存取找到random值的位置，再取值( O(1) )
line25 把此值拿出( O(n), relocate值 )
n = 1000000, 354秒完成



2.list, 必須每次都利用指標去找到目標位置, 再取出其值, 但是relocation成本低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <list>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>     // std::advance
using namespace std;

void shuffle( const int n ){
    // initialize a check vector
    list<int> cardVec;
    for( int i = 0 ; i < n ; i++ )
        cardVec.push_back(i);


    srand( time(NULL) );
    int leftCardNum = n;
    int nextPickedCard;
    list<int>::iterator numberErase;// temp pointer
    while( leftCardNum != 0 ){
        // pick a number m to choose the card at this location m
        nextPickedCard = rand( ) % leftCardNum;

        // advance to the position that chosen
        numberErase = cardVec.begin( );
        advance(numberErase, nextPickedCard);
        int picked = *numberErase;
        cout << picked << " ";
        cardVec.erase(numberErase);

        leftCardNum--;
    }
}

int main( ){
    cout << "The number you want to shuffle: ";

    int n;
    cin >> n;
    shuffle(n);
}

Note:
line26 找出第random值選到的那個人( O(n) ), 前進指標, line29可以直接刪除此位置的值( O(1), 不用relocate, 只需改指標的連結方式 )
n = 1000000, 238秒完成


作法三：

  1. O(n)
  2. 第一種實作法是延續作法二的問題來處理改進
克服上述relocation的問題：
relocation可以不用, 可以in-place完成：可以把一個陣列想成兩段,
後面m個是已經完成的shuffle的卡, 前面n-m個是尚未取出的卡

每次取卡時, 取出前面n-m個是尚未取出的卡中的一個, 與當前的(第n-m個)換位置, 直到皆取出

e.g. 1 2 3 4 5 6
1-6隨機取5, 1 2 3 4 5 6 , 6與第5個人換位置, 得到1 2 3 4 6 5
1-5隨機取5, 1 2 3 4 6 5 , 5與第5個人換位置, 得到1 2 3 4 6 5
1-4隨機取4, 1 2 3 4 6 5 , 4與第4個人換位置, 得到1 2 3 4 6 5
1-3隨機取1, 1 2 3 4 6 5 , 3與第1個人換位置, 得到3 2 1 4 6 5
1-2隨機取1, 3 2 1 4 6 5 , 2與第1個人換位置, 得到2 3 1 4 6 5
1-1隨機取1, 2 3 1 4 6 5 , 2與第1個人換位置, 得到2 3 1 4 6 5
(黃色表示未shuffle部分, 綠色表示目前考慮者, 紅色表示已shuffle者)

 此方法進入紅色部分後，其值就不會再改變
但是黃色部分會因為當前的人與他們其中一個換而不斷地在改變內容

C++ code:

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

void shuffle( const int n ){
    // initialize the array
    vector<int> cardVec;
    for( int i = 0 ; i < n ; i++ )
        cardVec.push_back( i );

    int undoneNumber = n;
    srand( 1 );

    int nextPickedCard;
    while( undoneNumber != 0 ){
        nextPickedCard = rand( ) % undoneNumber;

        // swap the number at index nextPickedCard with the number
        // at index undoneNumber-1
        int temp = cardVec[undoneNumber-1];
        cardVec[undoneNumber-1] = cardVec[nextPickedCard];
        cardVec[nextPickedCard] = temp;

        // consider next card
        undoneNumber--;
    }
}

int main( ){
    cout << "The number you want to shuffle: ";

    int n;
    cin >> n;
    shuffle(n);
}

Note:
n = 1000000, 2秒完成


----------
另一個實作方式是, 先shuffle前n-1張卡(子問題所在), 將第n張卡隨機與1~n張卡的其中一張交換 
e.g. 1 2 3 4 5 6
1-1隨機取1, 1 2 3 4 5 6, 1 與第1個位置換, 1 2 3 4 5 6
1-2隨機取1, 1 2 3 4 5 6, 2 與第1個位置換, 2 1 3 4 5 6
1-3隨機取3, 2 1 3 4 5 6, 3 與第3個位置換, 2 1 3 4 5 6
1-4隨機取2, 2 1 3 4 5 6, 4 與第2個位置換, 4 1 3 2 5 6
1-5隨機取2, 4 1 3 2 5 6, 5 與第2個位置換, 4 5 3 2 1 6
1-6隨機取2, 4 5 3 2 1 6, 6 與第2個位置換, 4 6 3 2 1 5
(黃色表示未shuffle部分, 綠色表示目前考慮者, 紅色表示已shuffle者)

 此方法仍在黃色部分的人，其值不會被改變

但是紅色部分會因為當前的人與他們其中一個換而不斷地在改變內容

C++ code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

void shuffle( const int n ){
    // initialize the array
    vector<int> cardVec;
    for( int i = 0 ; i < n ; i++ )
        cardVec.push_back( i );

    int undoneNumber = n;
    srand( 1 );

    int nextPickedCard;
    for( int i = 0 ; i < n ; i++ ){
        nextPickedCard = rand( ) % (i+1);

        // swap the element at nextPickedCard with current considering one
        int temp = cardVec[i];
        cardVec[i] = cardVec[nextPickedCard];
        cardVec[nextPickedCard] = temp;

    }

    for( int i = 0 ; i < n ; i++ )
        cout << cardVec.at( i ) << " ";

}

int main( ){
    cout << "The number you want to shuffle: ";

    int n;
    cin >> n;
    shuffle(n);
}

 作法三中，實作一和二小結：
改變的人不同，實作一是和尚未取出的人換位置
實作二是和取出的人換位置

reference:
張貼者： 於
標籤： , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)