Perfect shuffle: Difference between revisions
Content added Content deleted
(→{{header|Quackery}}: simplified shuffles) |
(Added Fortran solution candidate) |
||
Line 934: | Line 934: | ||
1024 10 |
1024 10 |
||
10000 300 |
10000 300 |
||
</pre> |
|||
=={{header|Fortran}}== |
|||
<lang fortran>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</lang> |
|||
<pre> |
|||
input (deck size) | output (number of shuffles required) |
|||
------------------------------------------------------- |
|||
8 | 3 |
|||
24 | 11 |
|||
52 | 8 |
|||
100 | 30 |
|||
1020 | 1018 |
|||
1024 | 10 |
|||
10000 | 300 |
|||
</pre> |
</pre> |
||