A perfect shuffle (or faro/weave shuffle) means splitting a deck of cards into equal halves, and perfectly interleaving them - so that you end up with the first card from the left half, followed by the first card from the right half, and so on:



 7♠ 8♠ 9♠ J♠ Q♠ K♠→7♠  8♠  9♠
  J♠  Q♠  K♠→7♠ J♠ 8♠ Q♠ 9♠ K♠


When you repeatedly perform perfect shuffles on an even-sized deck of unique cards, it will at some point arrive back at its original order. How many shuffles this takes, depends solely on the number of cards in the deck - for example for a deck of eight cards it takes three shuffles:





 original: 

1
2
3
4
5
6
7
8



 after 1st shuffle: 

1
5
2
6
3
7
4
8



 after 2nd shuffle: 

1
3
5
7
2
4
6
8



 after 3rd shuffle: 

1
2
3
4
5
6
7
8




The Task
 Write a function that can perform a perfect shuffle on an even-sized list of values.
 Call this function repeatedly to count how many shuffles are needed to get a deck back to its original order, for each of the deck sizes listed under "Test Cases" below.
 You can use a list of numbers (or anything else that's convenient) to represent a deck; just make sure that all "cards" are unique within each deck.
 Print out the resulting shuffle counts, to demonstrate that your program passes the test-cases.
Test Cases


 input (deck size) 
 output (number of shuffles required)


 8 
 3


 24 
 11


 52 
 8


 100 
 30


 1020 
 1018


 1024 
 10


 10000 
 300



# returns an array of the specified length, initialised to an ascending sequence of integers #
OP   DECK = ( INT length )[]INT:
     BEGIN
         [ 1 : length ]INT result;
         FOR i TO UPB result DO result[ i ] := i OD;
        result
     END # DECK # ;
 
# in-place shuffles the deck as per the task requirements #
# LWB deck is assumed to be 1 #
PROC shuffle = ( REF[]INT deck )VOID:
     BEGIN
         [ 1 : UPB deck ]INT result;
         INT left pos  := 1;
         INT right pos := ( UPB deck OVER 2 ) + 1;
         FOR i FROM 2 BY 2 TO UPB result DO
             result[ left pos  ] := deck[ i - 1 ];
             result[ right pos ] := deck[ i     ];
             left pos  +:= 1;
             right pos +:= 1
         OD;
         FOR i TO UPB deck DO deck[ i ] := result[ i ] OD
     END # SHUFFLE # ;
 
# compares two integer arrays for equality #
OP   = = ( []INT a, b )BOOL:
     IF LWB a /= LWB b OR UPB a /= UPB b
     THEN # the arrays have different bounds #
         FALSE
     ELSE
         BOOL result := TRUE;
         FOR i FROM LWB a TO UPB a WHILE result := a[ i ] = b[ i ] DO SKIP OD;
         result
     FI # = # ;
 
# compares two integer arrays for inequality #
OP   /= = ( []INT a, b )BOOL: NOT ( a = b );
 
# returns the number of shuffles required to return a deck of the specified length #
# back to its original state #
PROC count shuffles = ( INT length )INT:
     BEGIN
         []            INT original deck  = DECK length;
         [ 1 : length ]INT shuffled deck := original deck;
         INT   count         := 1;
         WHILE shuffle( shuffled deck );
               shuffled deck /= original deck
         DO
             count +:= 1
         OD;
         count
     END # count shuffles # ;
 
# test the shuffling #
[]INT lengths = ( 8, 24, 52, 100, 1020, 1024, 10 000 );
FOR l FROM LWB lengths TO UPB lengths DO
    print( ( whole( lengths[ l ], -8 ) + ": " + whole( count shuffles( lengths[ l ] ), -6 ), newline ) )
OD