Card shuffles
There are many techniques that people use to shuffle cards for card games. Some are more effective than others.
The task here is to implement the (seemingly) more common techniques of the riffle shuffle and overhand shuffle for n iterations. Implementing playing cards is not necessary if it would be easier to implement these shuffling methods for generic collections. Where possible, compare this to a standard/built-in shuffling procedure.
Bonus: Implement other methods described here. Allow for "human errors" of imperfect cutting and interleaving.
C++
<lang cpp>
- include <time.h>
- include <algorithm>
- include <iostream>
- include <string>
- include <deque>
class riffle
{
public:
void shuffle( std::deque<int>* v, int tm )
{
std::deque<int> tmp;
bool fl; size_t len; std::deque<int>::iterator it;
copyTo( v, &tmp );
for( int t = 0; t < tm; t++ ) { std::deque<int> lHand( rand() % ( tmp.size() / 3 ) + ( tmp.size() >> 1 ) ), rHand( tmp.size() - lHand.size() );
std::copy( tmp.begin(), tmp.begin() + lHand.size(), lHand.begin() ); std::copy( tmp.begin() + lHand.size(), tmp.end(), rHand.begin() ); tmp.clear();
while( lHand.size() && rHand.size() ) { fl = rand() % 10 < 5; if( fl )
len = 1 + lHand.size() > 3 ? rand() % 3 + 1 : rand() % ( lHand.size() ) + 1;
else len = 1 + rHand.size() > 3 ? rand() % 3 + 1 : rand() % ( rHand.size() ) + 1;
while( len ) { if( fl ) { tmp.push_front( *lHand.begin() ); lHand.erase( lHand.begin() ); } else { tmp.push_front( *rHand.begin() ); rHand.erase( rHand.begin() ); } len--; } }
if( lHand.size() < 1 ) { for( std::deque<int>::iterator x = rHand.begin(); x != rHand.end(); x++ ) tmp.push_front( *x ); } if( rHand.size() < 1 ) { for( std::deque<int>::iterator x = lHand.begin(); x != lHand.end(); x++ ) tmp.push_front( *x ); } } copyTo( &tmp, v );
}
private:
void copyTo( std::deque<int>* a, std::deque<int>* b )
{
for( std::deque<int>::iterator x = a->begin(); x != a->end(); x++ ) b->push_back( *x ); a->clear();
}
};
class overhand { public:
void shuffle( std::deque<int>* v, int tm )
{
std::deque<int> tmp; bool top; for( int t = 0; t < tm; t++ ) { while( v->size() ) { size_t len = rand() % ( v->size() ) + 1; top = rand() % 10 < 5; while( len ) { if( top ) tmp.push_back( *v->begin() ); else tmp.push_front( *v->begin() ); v->erase( v->begin() ); len--; } } for( std::deque<int>::iterator x = tmp.begin(); x != tmp.end(); x++ ) v->push_back( *x );
tmp.clear(); }
}
};
// global - just to make things simpler --------------------------------------------------- std::deque<int> cards;
void fill() {
cards.clear(); for( int x = 0; x < 20; x++ )
cards.push_back( x + 1 ); }
void display( std::string t ) {
std::cout << t << "\n"; for( std::deque<int>::iterator x = cards.begin(); x != cards.end(); x++ )
std::cout << *x << " ";
std::cout << "\n\n";
}
int main( int argc, char* argv[] ) {
srand( static_cast<unsigned>( time( NULL ) ) ); riffle r; overhand o;
fill(); r.shuffle( &cards, 10 ); display( "RIFFLE" ); fill(); o.shuffle( &cards, 10 ); display( "OVERHAND" ); fill(); std::random_shuffle( cards.begin(), cards.end() ); display( "STD SHUFFLE" );
return 0;
} </lang>
- Output:
RIFFLE 18 9 17 20 3 4 16 8 7 10 5 14 12 1 13 19 2 11 15 6 OVERHAND 2 13 12 11 10 9 18 17 6 5 4 3 7 20 19 15 8 14 16 1 STD SHUFFLE 14 4 17 3 12 5 19 6 20 2 16 11 8 15 7 13 10 18 9 1
J
<lang J>NB. cut rotates the deck to an arbitrary position overhand=: ;@|.@(<;.1~ 1 , 1 }. %@%:@# > # ?@# 0:)@]^:[
NB. Gilbert–Shannon–Reeds model riffle=: (({.~+/)`(I.@])`(-.@]#inv (}.~+/))} ?@(#&2)@#)@]^:[</lang>
Overhand shuffle is implemented not as was described in wikipedia but as described on the talk page "the cuts are taken from the top of the deck and placed on top of the new deck". The probability of a cut occurring between each pair of cards in this overhand shuffle is proportional to the reciprocal of the square root of the number of cards in the deck.
Task examples:
<lang J> 1 riffle i.20 0 1 2 3 4 5 6 7 8 13 14 9 15 16 17 10 18 11 12 19
10 riffle i.20
6 10 13 8 2 14 15 9 19 3 18 16 11 1 12 17 5 4 0 7
1 overhand i.20
17 18 19 14 15 16 11 12 13 0 1 2 3 4 5 6 7 8 9 10
10 overhand i.20
6 0 18 7 9 15 19 17 10 5 16 1 11 12 8 13 14 4 2 3</lang>
Java
<lang java5>import java.util.Arrays; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Random;
public class CardShuffles{
private static final Random rand = new Random();
public static <T> LinkedList<T> riffleShuffle(List<T> list, int flips){ LinkedList<T> newList = new LinkedList<T>();
newList.addAll(list);
for(int n = 0; n < flips; n++){ //cut the deck at the middle +/- 10%, remove the second line of the formula for perfect cutting int cutPoint = newList.size() / 2 + (rand.nextBoolean() ? -1 : 1 ) * rand.nextInt((int)(newList.size() * 0.1));
//split the deck List<T> left = new LinkedList<T>(); left.addAll(newList.subList(0, cutPoint)); List<T> right = new LinkedList<T>(); right.addAll(newList.subList(cutPoint, newList.size()));
newList.clear();
while(left.size() > 0 && right.size() > 0){ //allow for imperfect riffling so that more than one card can come form the same side in a row //biased towards the side with more cards //remove the if and else and brackets for perfect riffling if(rand.nextDouble() >= ((double)left.size() / right.size()) / 2){ newList.add(right.remove(0)); }else{ newList.add(left.remove(0)); } }
//if either hand is out of cards then flip all of the other hand to the shuffled deck if(left.size() > 0) newList.addAll(left); if(right.size() > 0) newList.addAll(right); } return newList; }
public static <T> LinkedList<T> overhandShuffle(List<T> list, int passes){ LinkedList<T> mainHand = new LinkedList<T>();
mainHand.addAll(list); for(int n = 0; n < passes; n++){ LinkedList<T> otherHand = new LinkedList<T>();
while(mainHand.size() > 0){ //cut at up to 20% of the way through the deck int cutSize = rand.nextInt((int)(list.size() * 0.2)) + 1;
LinkedList<T> temp = new LinkedList<T>();
//grab the next cut up to the end of the cards left in the main hand for(int i = 0; i < cutSize && mainHand.size() > 0; i++){ temp.add(mainHand.remove()); }
//add them to the cards in the other hand, sometimes to the front sometimes to the back if(rand.nextDouble() >= 0.1){ //front most of the time otherHand.addAll(0, temp); }else{ //end sometimes otherHand.addAll(temp); } }
//move the cards back to the main hand mainHand = otherHand; } return mainHand; }
public static void main(String[] args){ List<Integer> list = Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20); System.out.println(list); list = riffleShuffle(list, 10); System.out.println(list + "\n");
list = Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);
System.out.println(list); list = riffleShuffle(list, 1); System.out.println(list + "\n");
list = Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20); System.out.println(list); list = overhandShuffle(list, 10); System.out.println(list + "\n");
list = Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);
System.out.println(list); list = overhandShuffle(list, 1); System.out.println(list + "\n");
list = Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20); System.out.println(list); Collections.shuffle(list); System.out.println(list + "\n"); } }</lang>
- Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [20, 11, 1, 9, 15, 4, 19, 16, 8, 13, 7, 2, 14, 12, 10, 3, 17, 18, 6, 5] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [1, 12, 2, 3, 4, 5, 13, 14, 15, 6, 16, 7, 8, 9, 17, 18, 10, 19, 20, 11] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [20, 3, 10, 4, 2, 8, 1, 18, 13, 19, 14, 6, 9, 12, 16, 15, 5, 7, 11, 17] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [18, 19, 20, 17, 13, 14, 15, 16, 9, 10, 11, 12, 8, 6, 7, 3, 4, 5, 1, 2] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [18, 12, 13, 14, 2, 3, 15, 5, 9, 19, 7, 11, 1, 6, 4, 20, 16, 17, 10, 8]