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

From what I can see they all (David, Christian, Rob) DeBruijn sequence do NOT wrap (even with the proper substitutions) which means you cannot do multiple cuts with any assurance that it will work and the spectator cannot cut very thin nor very thick. These decks will have 5 cards at the end (or 5 at the beginning depending on your point of view) that will be duplicates or don't work. I tried to fix it but couldn't.

So I wrote my own debruin 52 (wraps) from scratch last month (took a lot of effort and a lot of luck) but the bit breakdown is 24, 28 and has 12 numbers outside the range 1-52 but wraps perfectly. I searched the internet to find another DeBruijn 52 and the only place I could find a true 52 wrapping DeBruijn is in Leo Boudreau's book Spirited Pasteboards lybrary.com under "Heady Stuff" published in 1987.

Leo's bit breakdown is 24, 28 and has 8 numbers outside the range 1-52. Of course neither mine nor Leo's deBruijn sequence has David/Christian's built in scheme but they are solid and wrap perfectly and I highly recommend Leo's DeBruijn 52 over mine because his has fewer values outside 1-52.
Glowball Yelnif.

Larry Finley created below 52 bit DeBruijn cycle in October 2018:
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 1 1 0 1 0 0 0 1
0 0 1 1 0 0 1 0 1 1 1
0 0 1 1 1 0 1 1 0 1 1 1 1
0 1 0 1 1
It is solid and wraps around perfectly.

To do David's "red card" trick do the following:
Using a plain deck of cards (not "one-way" and not red and blue backed) let's remove the 8D and 8H from the deck (the two red snowmen melted away). Now add two black jokers (no color red in them). Now arrange the 52 card deck as follows (note that the red cards ie Hearts and Diamonds will be in the "0" positions whereas the rest will be in the "1" positions).

Now you can do David's trick however you must take a month to memorize the position of all 52 cards before doing the trick (or tape a cheat sheet inside a "magic book" that you must reference when doing the trick).

Note: the reason for removing the two red cards is because my debruin sequence has 28 "1"s and 24 "0"s which means that you must add two jokers to fulfill the 28 requirement (for this particular trick). That leaves 24 zeros for the red cards and since there are 26 red cards in a full deck we must remove 2 red cards permanently from the deck. I remove the two snowman (the red 8s) because they melted away but your audience does not know this and does not care.

Note that for the traditional 6 card deBruijn trick using a one-way deck you do not have to remove any cards. A full 52 card deck (no Jokers) is fine, just orient the backs of the cards properly to correspond to the ones and zeros in the Yelnif 52 deBruijn pattern (see it in a few posts above).

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.