Shuffling the deck of cards perfectly randomly.

Problem

Write the program to shuffle the deck of cards in statistically random order.

 Knuth shuffle 

Simple way to shuffle the card in statistically random order is to use Knuth shuffle algorithm.

Basically, it mimics the shuffling the deck of cards by human as follows:

1. Pick one card randomly from the deck and remove it from the deck of chards an place the card in one of table.

2. Pick another card randomly from the deck and place it on the top of another card.

3. Repeat the step 2 until there is no card left.

At the end of this process, there will be a new deck of cards randomly shuffle.

I is important to choose correctly random generation library. In this practice code, I used std::uniform_real_distribution and std::default_random_engine.

Here is the complete code running in O(N).

	#include<iostream>
	#include<random>
	using namespace std;
	void swap(int * list, int s, int d)
	{
	int tmp = list[s];
	list[s] = list[d];
	list[d] = tmp;
	}
	void shuffle(int * list, int len)
	{
	uniform_real_distribution<double> distribution(0.0,1.0);
	default_random_engine generator;
	int n = len-1;
	for(int i = len-1; i >=0; i--)
	{
	double rn = (double)distribution(generator);
	int pos = rn*i;
	swap(list, i, pos);
	}
	}
	int main()
	{
	int input[10] = {1,2,3,4,5,6,7,8,9,10};
	for(int i =0 ; i < 100; i++)
	{
	shuffle(input, 10);
	cout<<"[";
	for (int j = 0; j < 10; j++)
	cout<<input[j]<<", ";
	cout<<"]"<<endl;
	}
	return 1;
	}

view raw random_shuffle.cpp hosted with ❤ by GitHub

Practice statistics:

29:00 to write up the code and fix up the logical flaws and typos.


Retried the same question in Python. (May 28 2019)
Did not apply the swap as in Knuth shuffle algorithm.


Python solution

	import random
	class ShuffleCard:
	def shuffle(self, input):
	cards = list(input)
	random.seed()
	new_deck = []
	while(len(cards) > 0):
	size = len(cards)
	pos = random.randint(0, size-1)
	next = cards[pos]
	new_deck.append(next)
	cards.remove(next)
	return new_deck
	cards = [i for i in range(60)]
	s = ShuffleCard()
	for i in range(5):
	print("shuffled = {}".format(s.shuffle(cards)))

view raw perfect_shuffle_cards.py hosted with ❤ by GitHub

Practice statistics:

15:00: to write up the code. Had to know how to use random module.