Following on from this post by Harry Garrood. This is an implementation in Python.
I don't read Haskell very well so took Harry's description of the method as well as his description of how to extract the cycle length of a permutation and then did my own Python thing.
Harrys's description of the task had a lovely animation to keep me on the right path but missed out one crucial step for me.
Harry states:
- Take one card from the top of the deck and discard it into a second pile.
- Take another card from the top of the deck, and put it at the bottom of the deck.
- Repeat these two steps, putting all discarded cards from step 1 into the same pile, until the original deck is all gone and the second pile has all the cards in it.
The above constitutes one shuffle but the next shuffle involves swappling the second for the first pile and then repeating by first discarding then "bottoming" for the next shuffle.
I had a variable set up to alternate between "discarding" and "bottoming" and initially did not re-initialize it on starting the next shuffle, so beware.
Algorithm in action
This was actually the last routine that I wrote, as I needed it to explain the algorithm with nice output:
In [16]:
def shuffleperms_tutor(cards='A2345'):
start, shuffles = list(cards), 0
deck2 = start[::]
fmt = '{!s:=^26} {!s:=^27} {!s:=^19}'
fm2 = fmt.replace('=^', '').replace('s', 'r', 2)
print(fmt.format('DECK', 'DECK2', 'COMMENT'))
while True:
deck, deck2, discard = deck2, [], True
print(fm2.format(deck, deck2, 'Shuffle {}'.format(shuffles)))
while deck:
if discard:
deck2.insert(0, deck.pop(0))
else:
deck.append(deck.pop(0))
print(fm2.format(deck, deck2,
'Post Discard' if discard else 'Post bottomming'))
discard = not discard
shuffles += 1
if deck2 == start:
break
return shuffles
In [17]:
shuffleperms_tutor(cards='A234')
Out[17]:
If you run
shuffleperms_tutor(cards='A2345') you get an equivalent to Harry's first example that begins===========DECK=========== ===========DECK2=========== ======COMMENT======` ['A', '2', '3', '4', '5'] [] Shuffle 0 ['2', '3', '4', '5'] ['A'] Post Discard ['3', '4', '5', '2'] ['A'] Post bottomming ['4', '5', '2'] ['3', 'A'] Post Discard ['5', '2', '4'] ['3', 'A'] Post bottomming ['2', '4'] ['5', '3', 'A'] Post Discard ['4', '2'] ['5', '3', 'A'] Post bottomming ['2'] ['4', '5', '3', 'A'] Post Discard ['2'] ['4', '5', '3', 'A'] Post bottomming [] ['2', '4', '5', '3', 'A'] Post Discard ['2', '4', '5', '3', 'A'] [] Shuffle 1 ...
No tutor
If you strip out the print statements to give the tutorial on algorithm progress; and switch to using a range of integers as the cards in the deck you get the following
In [18]:
def shuffleperms(cards):
start, shuffles = list(range(cards)), 0
deck2 = start[::]
while True:
deck, deck2, discard = deck2, [], True
while deck:
if discard:
deck2.insert(0, deck.pop(0))
else:
deck.append(deck.pop(0))
discard = not discard
shuffles += 1
if deck2 == start:
break
return shuffles
In [19]:
print([shuffleperms(i) for i in (4, 5, 52, 53, 100)])
Issues with naming
After learning what was happening I thoght of an improved(?) way to state the process that does not use the term "discard" and explicitely states what happens when going from one shuffle to another:
Alternate definition
Bruteforce algorithm:
- Start with an empty "deck" and a second deck of N different cards.
- Record the starting order of the second deck.
- If the first deck is empty then swap the decks and initialise the action on the first deck to be a "Transfer"
- Whilst there are cards in the first deck:
- Transfer the top card of the deck to the top of second deck
- Move the the resultant top card of the deck to the bottom of the first deck.
- Continue alternating steps 4.A and 4.B until all cards are eventually transferred to the second deck.
- This constitutes one shuffle of the deck back to the second deck
- If the order of cards in the second deck equals the starting order then return the number of shuffles; otherwise repeat from step 3.
Bruteforce it
This was my first implementation.
I had realised that the alternate transferring of a card then moving a card could be done by indexing of the list that is the deck of cards and wrote:
In [20]:
def shuffleperms_bruteforce(cards):
start, shuffles = list(range(cards)), 0
deck2 = start[::]
while True:
deck, deck2, transfer = deck2, [], True
while deck:
if transfer:
transfered, kept = deck[0::2], deck[1::2]
else:
transfered, kept = deck[1::2], deck[0::2]
transfer = transfer if len(deck) % 2 == 0 else not transfer
deck, deck2 = kept, transfered[::-1] + deck2
shuffles += 1
if deck2 == start:
break
return shuffles
print([shuffleperms_bruteforce(i) for i in (4, 5, 52, 53, 100)])
Cycle counting of a permutation.
Thanks must be given to Harry for a very enjoyable section explaining this method
- Do the first shuffle - which we now know produces the first
permutation - Extract the cycles mapping initial positions to items positions in the next permutation.
- Calculate the result as the lowest common multiple of the lengths of all the cycles.
An lcm routine
I actually had one hanging around from prior Rosetta Code tasks. You could use this:
In [21]:
import fractions
def lcm(a, b):
return int(abs(a * b) / fractions.gcd(a, b)) if a and b else 0
lcm(3, 7)
Out[21]:
The main cycle finding routine
In [22]:
def shuffleperms_permcycles(cards):
start, perm = _firstperm(cards)
permedto = [perm.index(i) for i in start]
cycles = _extract_cycles(start, permedto)
shuffles = reduce(lcm, (len(c) for c in cycles))
return shuffles
def _firstperm(cards):
deck, deck2, transfer = list(range(cards)), [], True
start = deck[::]
while deck:
if transfer:
transfered, kept = deck[0::2], deck[1::2]
else:
transfered, kept = deck[1::2], deck[0::2]
transfer = transfer if len(deck) % 2 == 0 else not transfer
deck, deck2 = kept, transfered[::-1] + deck2
return start, deck2
def _extract_cycles(start, permedto):
remains, cycles = start[::], []
while remains:
cycles.append([])
item, thiscycle = remains[0], cycles[-1]
while item in remains:
remains.remove(item)
thiscycle.append(item)
item = permedto[item]
return cycles
print([shuffleperms_permcycles(i) for i in (4, 5, 52, 53, 100)])
OEIS
The On-Line Encyclopedia of Integer Sequences doesn't seem to have this sequence of values:
In [23]:
[shuffleperms_permcycles(i) for i in range(1,20)]
Out[23]:
I would love to add it. It needs adding. My problem is that this task doesn't seem to have a proper name! It would be presumptious of me to name it, but if you have a reference to this shuffle that came with a name then please mention it in the comments.
No comments:
Post a Comment