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



MODULE PERFECT_SHUFFLE
     IMPLICIT NONE
 
     CONTAINS
 
     ! Shuffle the deck/array of integers
     FUNCTION SHUFFLE(NUM_ARR)
          INTEGER, DIMENSION(:), INTENT(IN) :: NUM_ARR
          INTEGER, DIMENSION(SIZE(NUM_ARR)) :: SHUFFLE
          INTEGER :: I, IDX
 
          IF (MOD(SIZE(NUM_ARR), 2) .NE. 0) THEN
              WRITE(*,*) "ERROR: SIZE OF DECK MUST BE EVEN NUMBER"
              CALL EXIT(1)
          END IF
 
          IDX = 1
 
          DO I=1, SIZE(NUM_ARR)/2
              SHUFFLE(IDX) = NUM_ARR(I)
              SHUFFLE(IDX+1) = NUM_ARR(SIZE(NUM_ARR)/2+I)
              IDX = IDX + 2
          END DO
 
    END FUNCTION SHUFFLE
 
    ! Compare two arrays element by element
    FUNCTION COMPARE_ARRAYS(ARRAY_1, ARRAY_2)
        INTEGER, DIMENSION(:) :: ARRAY_1, ARRAY_2
        LOGICAL :: COMPARE_ARRAYS
        INTEGER :: I
 
        DO I=1,SIZE(ARRAY_1)
            IF (ARRAY_1(I) .NE. ARRAY_2(I)) THEN
                COMPARE_ARRAYS = .FALSE.
                RETURN
            END IF
        END DO
 
        COMPARE_ARRAYS = .TRUE.
    END FUNCTION COMPARE_ARRAYS
 
    ! Generate a deck/array of consecutive integers
    FUNCTION GEN_DECK(DECK_SIZE)
        INTEGER, INTENT(IN) :: DECK_SIZE
        INTEGER, DIMENSION(DECK_SIZE) :: GEN_DECK
        INTEGER :: I
 
        GEN_DECK = (/(I, I=1,DECK_SIZE)/)
    END FUNCTION GEN_DECK
END MODULE PERFECT_SHUFFLE
 
! Program to demonstrate the perfect shuffle algorithm
! for various deck sizes
PROGRAM DEMO_PERFECT_SHUFFLE
    USE PERFECT_SHUFFLE
    IMPLICIT NONE
 
    INTEGER, PARAMETER, DIMENSION(7) :: DECK_SIZES = (/8, 24, 52, 100, 1020, 1024, 10000/)
    INTEGER, DIMENSION(:), ALLOCATABLE :: DECK, SHUFFLED
    INTEGER :: I, COUNTER
 
    WRITE(*,'(A, A, A)') "input (deck size)", " | ", "output (number of shuffles required)"
    WRITE(*,*) REPEAT("-", 55)
 
    DO I=1, SIZE(DECK_SIZES)
        IF (I .GT. 1) THEN
            DEALLOCATE(DECK)
            DEALLOCATE(SHUFFLED)
        END IF
        ALLOCATE(DECK(DECK_SIZES(I)))
        ALLOCATE(SHUFFLED(DECK_SIZES(I)))
        DECK = GEN_DECK(DECK_SIZES(I))
        SHUFFLED = SHUFFLE(DECK)
        COUNTER = 1
        DO WHILE (.NOT. COMPARE_ARRAYS(DECK, SHUFFLED))
            SHUFFLED = SHUFFLE(SHUFFLED)
            COUNTER = COUNTER + 1
        END DO
 
        WRITE(*,'(I17, A, I35)') DECK_SIZES(I), " | ", COUNTER
   END DO
END PROGRAM DEMO_PERFECT_SHUFFLE