Faro shuffle

The faro shuffle (American), weave shuffle (British), riffle shuffle, or dovetail shuffle is a method of shuffling playing cards. Mathematicians use "faro shuffle" for a shuffle in which the deck is split into equal halves of 26 cards that are then interwoven perfectly.^[1]

Magicians use these terms for a particular technique (which Diaconis, Graham, and Kantor call "the technique")^[2] for achieving this result. A right-handed practitioner holds the cards from above in the right and from below in the left hand. The deck is separated into two preferably equal parts by simply lifting up half the cards with the right thumb slightly and pushing the left hand's packet forward away from the right hand. The two packets are often crossed and tapped against each other to align them. They are then pushed together on the short sides and bent either up or down. The cards will then alternately fall onto each other, ideally alternating one by one from each half, much like a zipper. A flourish can be added by springing the packets together by applying pressure and bending them from above.^[3]

A game of faro ends with the cards in two equal piles that the dealer must combine to deal them for the next game. According to the magician John Maskelyne, the above method was used, and he calls it the "faro dealer's shuffle".^[4] Maskelyne was the first to give clear instructions, but the shuffle was used and associated with faro earlier, as discovered mostly by the mathematician and magician Persi Diaconis.^[5]

A faro shuffle that leaves the original top card at the top and the original bottom card at the bottom is known as an out-shuffle; one that moves the original top card to second and the original bottom card to second from the bottom is known as an in-shuffle. These names were coined by the magician and computer programmer Alex Elmsley.^[6] A perfect faro shuffle, where the cards are perfectly alternated, is considered one of the most difficult sleights of card manipulation, because it requires the shuffler to cut the deck into two equal stacks and apply just the right pressure when pushing the half decks into each other.

The faro shuffle is a controlled shuffle that does not fully randomize a deck. If one manages to perform eight perfect faro out-shuffles in a row, then the deck of 52 cards will be restored to its original order. If one can do perfect in-shuffles, then 26 shuffles will reverse the order of the deck and 26 more will restore it to its original order.^[7]

Computer-science aspects

A faro shuffle is not to be confused with a sorting algorithm. A perfect faro shuffle cycles the order of the cards into a fixed number of states. For a 52-card deck using perfect faro out-shuffles, there are 8 possible states in the cycle. That is, a faro shuffle can only be used to return the deck to its order prior to faro shuffling; it will not sort a randomized deck, nor can it return a randomized deck to new-deck order (unless the randomized initial state of the deck just happens to be one of the permutations of faro-shuffling a new deck).

In-shuffles and out-shuffles are used in computer algorithms, notably in parallel computing.^[8]

Below is a Python 3 implementation of a perfect faro out-shuffle:

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Deck(object):
    def __init__(self):
        self.cards = [
            'A♠', '2♠', '3♠', '4♠', '5♠', '6♠', '7♠', '8♠', '9♠', '10♠', 'J♠',
            'Q♠', 'K♠', 'A♦', '2♦', '3♦', '4♦', '5♦', '6♦', '7♦', '8♦', '9♦',
            '10♦', 'J♦', 'Q♦', 'K♦', 'K♣', 'Q♣', 'J♣','10♣', '9♣', '8♣', '7♣',
            '6♣', '5♣', '4♣', '3♣', '2♣', 'A♣', 'K♥', 'Q♥','J♥', '10♥', '9♥', 
            '8♥', '7♥', '6♥', '5♥', '4♥','3♥', '2♥', 'A♥']
    def __eq__(self, other):
        return self.cards == other.cards

    def faro_shuffle(self):
        '''Shuffles the deck using a perfect faro shuffle.'''
        r = []
        for (a, b) in zip(self.cards[0:26], self.cards[26:]):
            r.append(a)
            r.append(b)
        self.cards = r

original_deck = Deck()  # A deck in new-deck-order we will use for comparison.
shuffled_deck = Deck()  # A deck we will repeatedly faro-shuffle.

for i in range(1, 1000):
    shuffled_deck.faro_shuffle()
    if shuffled_deck == original_deck:
        print("Deck is back in new-deck order after %s shuffles." % i)
        break

The program shuffles a 52-card deck until it returns to its original order. This happens in exactly 8 iterations (shuffles):

(prompt)> python shuffle.py

The deck is back in new-deck order after 8 shuffles.

Below is a Perl implementation of a perfect out-faro shuffle:

#!/usr/bin/perl
# File:  faro_shuffle.pl
# Usage:  perl faro_shuffle.pl
# Purpose:  To discover how many out-faro shuffles are required to
#           revert a deck of 52 cards back to its original order.

use strict;
use warnings;

# Given an input of 52 elements (cards), returns them
# as if they were shuffled with an out-faro shuffle:
sub faroShuffle
{
   # Verify that there are exactly 52 inputs:
   use Carp;
   croak "faroShuffle() requires 52 elements"  unless @_ == 52;

   return map { @_[$_, $_+26] } (0 .. 25);
}

# Define a deck in new-deck order that we will use for comparison:
my @originalDeck = qw(
   AH  2H  3H  4H  5H  6H  7H  8H  9H 10H  JH  QH  KH  
   AC  2C  3C  4C  5C  6C  7C  8C  9C 10C  JC  QC  KC  
   KD  QD  JD 10D  9D  8D  7D  6D  5D  4D  3D  2D  AD  
   KS  QS  JS 10S  9S  8S  7S  6S  5S  4S  3S  2S  AS  
);

# Create a deck that we will repeatedly faro-shuffle:
my @shuffledDeck = @originalDeck;

foreach my $i (1 .. 1000)
{
   @shuffledDeck = faroShuffle(@shuffledDeck);

   if ("@shuffledDeck" eq "@originalDeck")
   {
      print "The deck is back in new-deck order after $i out-faro shuffles.\n";
      last;
   }
}

__END__

The program shuffles a 52-card deck until it returns to its original order. This happens in exactly 8 iterations (shuffles):

(prompt)> perl faro_shuffle.pl

The deck is back in new-deck order after 8 out-faro shuffles.

Below is a Perl 6 implementation of a perfect out-faro shuffle:

#!/usr/bin/perl6
# File:  faro_shuffle.p6
# Usage:  perl6 faro_shuffle.p6
# Purpose:  To discover how many out-faros shuffles are required to
#           revert a deck of 52 cards back to its original order.

use v6;

# Define a deck in new-deck order that we will use for comparison:
my @originalDeck = <
   AH  2H  3H  4H  5H  6H  7H  8H  9H 10H  JH  QH  KH  
   AC  2C  3C  4C  5C  6C  7C  8C  9C 10C  JC  QC  KC  
   KD  QD  JD 10D  9D  8D  7D  6D  5D  4D  3D  2D  AD  
   KS  QS  JS 10S  9S  8S  7S  6S  5S  4S  3S  2S  AS  
>;

# Create a deck that we will repeatedly faro-shuffle:
my @deck = @originalDeck;

for 1 .. * -> $i
{
   @deck = flat @deck[0 .. */2-1] Z @deck[*/2 .. *-1];  # the faro shuffle
   next  unless @deck eqv @originalDeck;  # if no match, repeat

   # We got a match!  Report and break out:
   print "The deck is back in new-deck order after $i out-faro shuffles.\n";
   last;
}

=finish

The program shuffles a 52-card deck until it returns to its original order. This happens in exactly 8 iterations (shuffles):

(prompt)> perl6 faro_shuffle.p6

The deck is back in new-deck order after 8 out-faro shuffles.

Group theory aspects

In mathematics, a perfect shuffle can be considered an element of the symmetric group.

More generally, in $S_{2n}$ , the perfect shuffle is the permutation that splits the set into 2 piles and interleaves them:

\begin{pmatrix} 1 & 2 & 3 & 4 & \cdots \\ 1 & n+1 & 2 & n+2 & \cdots \end{pmatrix}

In other words, it is the map

k \mapsto \begin{cases} \left \lceil \frac{k}{2} \right \rceil & k \ \text{odd}\\ n+\frac{k}{2} & k \ \text{even} \end{cases}

Analogously, the $(k,n)$ -perfect shuffle permutation^[9] is the element of $S_{kn}$ that splits the set into k piles and interleaves them.

The $(2,n)$ -perfect shuffle, denoted $\rho_n$ , is the composition of the $(2,n-1)$ -perfect shuffle with an $n$ -cycle, so the sign of $\rho_n$ is:

\mbox{sgn}(\rho_n) = (-1)^{n+1}\mbox{sgn}(\rho_{n-1}).

The sign is thus 4-periodic:

\mbox{sgn}(\rho_n) = (-1)^{\lfloor n/2 \rfloor} = \begin{cases} +1 & n \equiv 0,1 \pmod{4}\\ -1 & n \equiv 2,3 \pmod{4} \end{cases}

The first few perfect shuffles are: $\rho_0$ and $\rho_1$ are trivial, and $\rho_2$ is the transposition $(23) \in S_4$ .

References

Diaconis, P.; Graham, R. L.; Kantor, W. M. (1983). "The mathematics of perfect shuffles" (PDF). Advances in Applied Mathematics 4 (2): 175–196. doi:10.1016/0196-8858(83)90009-X.

Ellis, J.; Fan, H.; Shallit, J. (2002). "The Cycles of the Multiway Perfect Shuffle Permutation" (PDF). Discrete Mathematics and Theoretical Computer Science 5: 169–180. Retrieved 26 Dec 2013.

Maskelyne, John (1894). Sharps and Flats: A Complete Revelation of the Secrets of Cheating at Games of Chance and Skill. Longmans, Green and Company. Retrieved 26 Dec 2013.

Morris, S. Brent (1998). Magic Tricks, Card Shuffling, and Dynamic Computer Memories. The Mathematical Association of America. ISBN 0-883-85527-5. Retrieved 26 Dec 2013.

Footnotes

↑ Morris 1998, 13
↑ , Diaconis, Graham, and Kantor 1983, 188
↑ Morris 1998, 111
↑ Maskelyne 1894, 204
↑ Morris 1998, 8
↑ Morris 1998, 11–12
↑ Diaconis, Graham, and Kantor 1983, 193
↑ Diaconis, Graham, and Kantor 1983, 191–193
↑ Ellis, Fan, and Shallit 2002

This article is issued from Wikipedia - version of the Wednesday, April 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Faro shuffle

Computer-science aspects

Group theory aspects

See also

References

Footnotes