How many perfect shuffles until the deck is back in order? 2

[motoslide]

I hope it's OK to post a puzzle without knowing the answer. If not, just hook me up to the high-voltage lines and let me fry.
I'd like to see a method to determine how many times a person would need to shuffle a deck of 52 cards until they are back in their original order.
The definition of a perfect shuffle would be to always cut the deck into 2 piles of 26 cards. The top card (top stack) will always end up on top. The remaining are interleaved in perfect succession. Assuming the cards can be represented by unique numbers 1-52:

Before the first shuffle:
1,2,3,4,5 ... 48,49,50,52,51

After the first shuffle we'd have:
1,27,2,28,3,29 ... 25,51,26,52

After two shuffles:
1,14,27,40,2,15 ... 13,26,39,52

After the Nth shuffle:
1,2,3,4,5 ... 48,49,50,51,52

Any takers?

 

[gmmastros]

Uhhh, by my calculations... the answer is [!]8[/!].

The VB6 solution....

[white]Option Explicit

Private Sub Command1_Click()
    
    Dim i As Long
    Dim Deck() As Long
    Dim iShuffleCount As Long
    
    ReDim Deck(1 To 52)
    
    For i = 1 To 52
        Deck(i) = i
    Next
    
    Call DebugPrintDeck(Deck)
    
    Call Shuffle(Deck)
    iShuffleCount = 1
    Call DebugPrintDeck(Deck)
    
    While Not InOrder(Deck)
        Call Shuffle(Deck)
        iShuffleCount = iShuffleCount + 1
        Call DebugPrintDeck(Deck)
    Wend
    
    Call MsgBox("Shuffles:  " & CStr(iShuffleCount))
    
End Sub

Private Sub Shuffle(ByRef Deck() As Long)
    
    Dim i As Long
    Dim iIndex As Long
    Dim NewDeck() As Long
    
    ReDim NewDeck(1 To 52)
    
    iIndex = 1
    For i = 1 To 26
        NewDeck(iIndex) = Deck(i)
        NewDeck(iIndex + 1) = Deck(i + 26)
        iIndex = iIndex + 2
    Next
        
    Deck = NewDeck
    
End Sub

Private Function DebugPrintDeck(ByRef Deck() As Long)
    
    Dim cTemp As String
    Dim i As Long
    
    For i = LBound(Deck) To UBound(Deck)
        cTemp = cTemp & CStr(Deck(i)) & ","
    Next
    
    cTemp = Left(cTemp, Len(cTemp) - 1)
    
    Debug.Print cTemp
    
End Function

Private Function InOrder(ByRef Deck() As Long) As Boolean
    
    Dim i As Long
    Dim bResult As Boolean
    
    bResult = True
    For i = LBound(Deck) To UBound(Deck)
        If Deck(i) <> i Then
            bResult = False
            Exit For
        End If
    Next
    
    InOrder = bResult
    
End Function
[/white]

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom

 

[mharroff]

8 using VBA

[COLOR=white]

Sub Shuffle()
Dim strOriginalDeck As String
Dim strShuffled As String
Dim x As Integer
Dim y As Integer
Dim varArray1(52) As Variant
Dim varArray2(52) As Variant
Dim intShuffles As Integer


For x = 1 To 52
  strOriginalDeck = strOriginalDeck & x
  varArray1(x) = x
Next
strShuffled = ""
Do Until strShuffled = strOriginalDeck
  strShuffled = ""
  intShuffles = intShuffles + 1
  y = 0
  For x = 1 To 26
    y = y + 1
    varArray2(y) = varArray1(x)
    y = y + 1
    varArray2(y) = varArray1(x + 26)
  Next
  For x = 1 To 52
    strShuffled = strShuffled & varArray2(x)
    varArray1(x) = varArray2(x)
  Next
Loop
MsgBox intShuffles
End Sub
[/color]

 

[motoslide]

I guess I should have continued my manual method a bit longer before posting. I was half way there!
I'm impressed with the speed of these answers, and I appologize that it wasn't more of a challenge.

 

[strongm]

As an amateur card magician I should point out that we've only got one of the answers; it depends whether we're doing an inshuffle (which is what everyone is modelling here so far) or an outshuffle ...

 

[strongm]

(oops: it is the outshuffle that everyone has been modelling)

 

[PHV]

As I'm am unix guy, here an awk solution:

[white]awk '
function deck(d ,i,x){
  for(i=1;i<=52;++i)x=x" "d[i]
  print x;return x
}
BEGIN{
 for(i=1;i<=52;++i)C[i]=i;c=deck(C)
 while(c!=s){
  ++t;j=0
  for(i=1;i<=26;++i){S[++j]=C[i];S[++j]=C[26+i]}
  s=deck(S);for(i=1;i<=52;++i)C[i]=S[i]
 }; print t" perfect shuffles"
}
'[/white]

Hope This Helps, PH.
Want to get great answers to your Tek-Tips questions? Have a look at FAQ219-2884 or FAQ181-2886

 

[Mike Lewis]

I know nothing about card games, so please excuse me if I'm talking rubbish. But surely a "perfect shuffle" is one where the new sequence is completely random. After all, any form of shuffling in which the new sequence can be predicted is not really shuffling.

Mike


__________________________________
Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

 

[Diancecht]

Not exactly:

http://www.jimloy.com/math/shuffle.htm

Cheers,
Dian

 

[vongrunt]

Frell, I forgot how for() loop looks like :

(SQL, M$ Edition)

[white]select distinct colid-1 as rowno, (colid-1)%2*26+(colid+1)/2 as cardno
into #blah
from msdb..syscolumns where colid between 1 and 52

declare @N int; set @N = 1
while 1 <> any(select cardno-rowno from #blah)
begin
	update A set cardno = B.cardno
	from #blah A
	inner join #blah B on B.rowno=A.rowno%2*26+A.rowno/2

	set @N = @N+1
end

select @N
drop table #blah[/white]

------
[small]select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')[/small]

 

[mharroff]

In my previous code changing this:

  For x = 1 To 26

    y = y + 1

    varArray2(y) = varArray1(x)

    y = y + 1

    varArray2(y) = varArray1(x + 26)

  Next

to this:

  For x = 1 To 26

    y = y + 1

    varArray2(y) = varArray1(x + 26)

    y = y + 1

    varArray2(y) = varArray1(x)

  Next

you find that it takes 52 in shuffles to return the deck to original position

 

[strongm]

Correct

 

[BoxHead]

There are two types of perfect shuffles, the "in-shuffle" and the "out-shuffle." Let's assume that the deck is divided in two with the top cards going into the left hand and the bottom cards into the right hand. Then an in-shuffle begins with the first card coming from the left, the second from the right, the third from the left, etc.

With the in-shuffle, the top card is always the top card and the answer is 8.


This is one of those things that I can to work in practice but not in theory. In my youth, I did card tricks and usually started by letting people see the deck was shuffled (after I had done 5 in-shuffles). then, while talking about trick cards and trick decks, I'd do 3 more faro shuffles and let them see that the deck was an ordinary deck with all of the cards in Ace to King order by suit.

What I can't get my brain wrapped around is the fact that with 52 cards, 8 in-shuffles gets you back to your starting position. With 12 cards, it takes 10 in-shuffles.


Is there a logic or formula behind this?