de Bruijn sequence for a card trick

README.md

A card trick based on a de Bruijn sequence

Encode cards as 6-digit binary strings. Arrange them following a de Bruijn sequence. Get someone to draw 6 cards, and tell you their colours. You can tell them exactly which cards they have.

Written up on The Aperiodical at http://aperiodical.com/2012/08/davids-de-bruijn-sequence-card-trick/

debruijn.py

# de Bruijn card trick computatorator
# by Christian Perfect
# based on a trick by Persi Diaconis and Ron Graham

#names of cards
faces = ['King','Ace','2','3','4','5','6','7','8','9','10','Jack','Queen']
suits = ['Diamonds','Clubs','Hearts','Spades']

#generate de bruijn sequence
sequence = [0,0,0,0,0,1]
for i in range(6,64):
	sequence.append( (sequence[i-6]+sequence[i-5]) % 2 )

#get a string of binary digits representing an integer
def binarise(n,length):
	digits=[]
	while n>0:
		digits.insert(0,int(n%2))
		n=(n-n%2)/2
	digits = [0]*(length-len(digits))+digits	#pad to the desired length
	return digits

#decode a string of binary digits to an integer
def debinarise(digits):
	n=0
	for i in digits:
		n*=2
		n+=i
	return n

#decode a six-digit binary string to a card
def decode_sequence(seq):
	number = debinarise(seq[:4])
	suit = debinarise(seq[4:])
	return number,suit

#turn a card into a six-digit binary string
def encode_card(card):
	number,suit = card
	return ''.join([str(x) for x in binarise(number,4)+binarise(suit,2)])

#display a card's binary encoding and its name
def show_card(card):
	number,suit = card
	return '%s: %s of %s' % (encode_card(card), faces[number], suits[suit])


# The actual computation!
sequence*=2	#take two copies of the sequence to cope with the cycle at the end

# Get the ordering of the (64, not all real) cards from the sequence
cards = [decode_sequence(sequence[i:i+6]) for i in range(0,64)]

# The deck of cards consists of the first 52
deck = cards[:52]

# Get the unused cards from the end of the 64-deck which have usable values
castoffs = [(x,y) for (x,y) in cards[52:] if x<13]
# Separate them into red and black
castoffs_red = [(x,y) for (x,y) in castoffs if y%2==0]
castoffs_black = [(x,y) for (x,y) in castoffs if y%2==1]

# Get the cards from the 52-deck that don't have usable values
toswap = [(x,y) for (x,y) in deck if x>=13]
swaps = {}

# Match up bad cards in the 52-deck with good cards in the castoffs
for card in toswap:
	number,suit = card
	b=castoffs_red.pop() if suit%2==0 else castoffs_black.pop()
	swaps[card]=b

# Show the resulting ordering of the real 52-card deck
for i in range(0,52):
	digits = sequence[i:i+6]
	card = decode_sequence(digits)
	if card in swaps.keys():
		card = swaps[card]
	print(show_card(card))

# Show which bad codes are swapped with which good ones
print('Swaps')
for a,b in swaps.items():
	print('%s -> %s' % (encode_card(a),show_card(b)))

output.txt

000001: Ace of Clubs
000010: Ace of Hearts
000100: 2 of Diamonds
001000: 3 of Diamonds
010000: 5 of Diamonds
100001: 9 of Clubs
000011: Ace of Spades
000110: 2 of Hearts
001100: 4 of Diamonds
011000: 7 of Diamonds
110001: King of Clubs
100010: 9 of Hearts
000101: 2 of Clubs
001010: 3 of Hearts
010100: 6 of Diamonds
101001: Jack of Clubs
010011: 5 of Spades
100111: 10 of Spades
001111: 4 of Spades
011110: 8 of Hearts
011111: 8 of Spades
000000: Ace of Diamonds
100000: 9 of Diamonds
101000: Jack of Diamonds
010001: 5 of Clubs
100011: 9 of Spades
000111: 2 of Spades
001110: 4 of Hearts
011100: 8 of Diamonds
101111: Queen of Spades
110010: King of Hearts
100100: 10 of Diamonds
001001: 3 of Clubs
010010: 5 of Hearts
100101: 10 of Clubs
001011: 3 of Spades
010110: 6 of Hearts
101101: Queen of Clubs
011011: 7 of Spades
010111: 6 of Spades
101110: Queen of Hearts
011101: 8 of Clubs
101011: Jack of Spades
110000: King of Diamonds
101100: Queen of Diamonds
011001: 7 of Clubs
110011: King of Spades
100110: 10 of Hearts
001101: 4 of Clubs
011010: 7 of Hearts
010101: 6 of Clubs
101010: Jack of Hearts
Swaps
110101 -> 010101
110110 -> 110000
110111 -> 010111
111101 -> 011111
111001 -> 101111
111011 -> 101011
111010 -> 000000
110100 -> 100000

Here is a 26-26 wrapping De Bruijn given to me by TomasB from Sweden that is even better (no need to remove two red cards nor add two Jokers).
1110110000100110111100101110101101000101010010000011
Of course you will either have to memorize your deck and/or create a cheat sheet of some kind to work with it.