Friday, April 22, 2016

Fisher-Yates algorithm

April 22, 2016

A deck of cards is represented by an integer array of size 52, with possible value of 1 - 13 for each position. Design an algorithm to shuffle the deck of cards in linear time, in-place.

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

April 26, 2016
http://www.geeksforgeeks.org/shuffle-a-given-array/

“shuffle a deck of cards” or “randomize a given array”

Question and answer:

1. Understand the naive approach, extra space - an array, and also time O(n^2).

2. Came cross this blog <- So, use Fisher-Yates algorithm

大概就是取一个array里的任意n个不同的值,得到一个随机的组合,不能取同一个index的数,但是可以取数值相同的不同index的数

给一个array:[5,1,3,3],
再给一个数字n:2,
求这个array里的任意num个数:比如可以得到[5,1] or [5,3] or [1,3] or [3,3] ,但是不能得到[5,5]

再比如[5,1,3,3], 1 ===> [5] or [1] or [3]

就是先判断如果n>array.length或者n<=0或者array是空,返回一个空array
否则就是一个loop,每一次生成一个random的index数字,还用了一个hashset来存之前访问过的index,如果生成的random index之前已经get了,就再继续生成一个random index。
loop n次,每次取到的值放进新的结果array里。.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
然后说了说也可以用一个boolean array存每个值有没有已经取到。。
写完后再写了写unit test什么的,还有问道怎么检测得到的结果比如[5,1]确实是[5,1,3,3]里的
Julia's comment: 
3 issues:
1. In place - no extra array 
2. Hashset is also extra memory 
3. Work on array index - random number selection using % operator, not on value in the array. 

3. Let us walk through the code and then add comments - make it fun memory:
// A function to generate a random permutation of arr[]
void randomize ( int arr[], int n )
{
    // Use a different seed value so that we don't get same
    // result each time we run this program
    srand ( time(NULL) ); // Julia, Good to know, C++, look up srand API
    // Start from the last element and swap one by one. We don't
    // need to run for the first element that's why i > 0
    for (int i = n-1; i > 0; i--)
    {
        // Pick a random index from 0 to i
        int j = rand() % (i+1); // Julia: random number -> Range (0, i) using module
        // Swap arr[i] with the element at random index
        swap(&arr[i], &arr[j]); // swap two nodes
    }

No comments:

Post a Comment