| A question I've wondered about is whether or not every possible permutation of the deck can be reached by riffle shuffling. As the article notes, a 1 card riffle can move the card at the end of the deck to any position within the deck, leaving the other cards undisturbed, so obviously you can reach any permutation by a series of 1 card riffles. What about if you can only use "believable" riffles? By "believable" I mean that the cut is near the middle of the pack, and the alternate left and right drops are mostly small and about the same size. The answer is yes, you can reach every permutation. Let P be a perfect out riffle shuffle. Let S(n) be an almost perfect out riffle shuffle, differing only in that when the cards that would end up n and n+1 from the bottom are the next two cards to drop in a perfect out riffle you drop switch the order they drop. S(n) is a believable riffle. The result of applying S(n) is the same as if you applied P and then swapped the two cards that are n and n+1 from the bottom. Let O(R), where R is any shuffle, be the minimum number of time you have to apply R consecutively before the deck returns to its starting order. (By "starting order" I mean the order it was in before you applied the O(R) R shuffles). For example, O(P) = 8, because 8 perfect out riffle shuffles leaves the deck in the order you started with. If you take a deck, do O(S(n))-1 shuffles using S(n), followed by one perfect out riffle P, the result is that the deck is back to its original order except that the cards at n and n+1 from the bottom are swapped. Since you can produce any permutation by a serious of swaps of adjacent items (hello, Bubble Sort!), this shows you can reach any permutation by a series of believable riffles. This is not necessarily an efficient way to achieve a given permutation, but hey, my bachelor's degree is in pure math, not applied math--efficiency is someone else's problem. :-) Swapping n and n+1 with the above procedure takes: 72 shuffles for n = 0 or 50
56 shuffles for 1 or 49
40 shuffles for 16, 17, 33, or 34
120 shuffles for 22 or 28
16 shuffles for everything else
Here's some Python code to play with this [1]. It takes n as an argument, and just does the O(S(n))-1 shuffles with S(n) followed by a perfect out riffle and then displays what cards ended up moved, along with how many total shuffles were done.Probably not very efficient, as it was just a quickie for when I was playing around with this problem. (One shortcut it takes that might be confusing if you are not familiar with group theory. It does not actually do O(S(n))-1 applications of S(n). It takes advantage of the fact that the permutation you get by applying a permutation, R, O(R)-1 times is the same as applying the inverse permutation, R', once. So it actually just computes S'(n) and then applies S'(n) and P to the deck). PS: if you apply S(n) once followed by P seven times, the result is to swap card (n+1)//2 with n/2+26 if n is even, or with (n+1)/2+25 if n is odd. If you do S(n), 7 P, S(n+1), 7 P, S(n), 7 P you get swaps of consecutive cards. If n is even, you swap n/2 with n/2+1. If n is odd, you swap the cards that are 26 past the cards that doing this for n-1 would have swapped. That gives you a procedure for swapping any adjacent pair in 24 shuffles. That beats the original procedure I have for 10 values of n. [1] https://pastebin.com/bZW5ine7 |