Perfect shuffle
A deck can be divided in two halves:
a b c d e f -> a b c | d e f
Perfect shuffling means taking one card from the first half, one card for the second half, and so on:
a d b e c f
Perfect shuffling can be done only with an even number of cards.
A remarkable feature of perfect shuffling is that the deck goes back to the start after a number that is fixed for every n (where n is the number of cards)
- Implement a magic shuffle function
- Print the number of perfect shuffles needed to go back to start for decks from 2 to 10,000 cards (by steps of 2), determined by using the magic shuffle function
Python
<lang python> import doctest import random
def flatten(lst):
""" >>> flatten([[3,2],[1,2]]) [3, 2, 1, 2] """ return [i for sublst in lst for i in sublst]
def magic_shuffle(deck):
""" >>> magic_shuffle([1,2,3,4]) [1, 3, 2, 4] """ half = len(deck) // 2 return flatten(zip(deck[:half], deck[half:]))
def after_how_many_is_equal(shuffle_type,start,end):
""" >>> after_how_many_is_equal(magic_shuffle,[1,2,3,4],[1,2,3,4]) 2 """
start = shuffle_type(start) counter = 1 while start != end: start = shuffle_type(start) counter += 1 return counter
def main():
doctest.testmod()
print("Length of the deck of cards | Perfect shuffles needed to obtain the same deck back") for length in range(2,10**4,2): deck = list(range(length)) shuffles_needed = after_how_many_is_equal(magic_shuffle,deck,deck) print("{} | {}".format(length,shuffles_needed))
if __name__ == "__main__":
main()
</lang> Reversed shuffle or just calculate how many shuffles are needed: <lang python>def mul_ord2(n): # directly calculate how many shuffles are needed to restore # initial order: 2^o mod(n-1) == 1 if n == 2: return 1
n,t,o = n-1,2,1 while t != 1: t,o = (t*2)%n,o+1 return o
def shuffles(n): a,c = list(range(n)), 0 b = a
while True: # Reverse shuffle; a[i] can be taken as the current # position of the card with value i. This is faster. a = a[0:n:2] + a[1:n:2] c += 1 if b == a: break return c
for n in range(2, 10000, 2): #print(n, mul_ord2(n)) print(n, shuffles(n))</lang>