Sunday, June 21, 2009

Shuffle functions

Very frequency asked question is "Write a program to shuffle a set of cards". There are many approaches to solve this problem.

Almost all of them treat the set of cards as a list and write the program to shuffle the list.

One approach is to emulate the human shuffling:
Hindu Shuffle; Riffle shuffle

Other techniques are discussed in more details in wikipedia

Here is an interesting but not optimal way(O(n lgn)) to shuffle a list:
In Ocaml:
let shuffle l1 =
let sortComparator x y =
(
match (Random.int 3) with
0 -> 0
| 1 -> -1
| 2 -> 1
| _ -> failwith "Error in shuffle"
)
in
List.sort sortComparator l1
;;

C++ Code:

template < class T >
bool sortComparator(T x, T y){
if(rand % 2 == 0)
true;
else
false
}

template < class T >
vector < t > shuffle(vector < t > cards) {
sort(cards.begin(), cards.end(), sortComparator);
return cards;
}

No comments: