After all the examples given, I need to give something back. The contributions are sort of like making a pie; lots of ingredients go in, get mixed around, and the end result is something tasty.
While Matthew was so generous with his code/examples I was looking and looking for various solutions and found:
http://www.rosettacode.org/wiki/Rosetta_Code
I put permutations in the search box and was presented with code examples in many, many languages. It took me a minute to continue because I got kinda misty seeing all my old friends. I started with FORTRAN in 1966 and have worked with so many languages. Now a lifetime of different syntaxes is more a hindrance than a help. Along the way, this young whippersnapper of a language appeared called “C”. I thought, “Just another syntax, wonder how long that will be around?” and didn’t bother to learn it. What did Scully (Dana) tell Mr. Bruckman, “There are misses and then there are misses.”
Back to permutations … I hope this isn’t heresy but at this stage, I’m more comfortable with my “first” language, FORTRAN. So I popped the example below into Simply Fortran. It generated all 12! in about 6 seconds. Then I read my 6.2GB file of pre-generated 12! (thanks to Matthew) numbers. that took 126 seconds.
So it’s faster to generate them on the fly than it is to read them from a file.
Rosetta/permutations/FORTRAN gave a speed program with four different algorithms. The example below uses the fastest of the four.
**** WARNING **** This is FORTRAN CODE
program Base12Solver
implicit none
integer nmax
integer, dimension(:), allocatable :: ida
integer i
integer(8) ic
integer clock_rate, clock_max, t1, t2
real(8) dt
!
!
! Beginning:
!
nmax = 12
allocate ( ida(1:nmax) )
!
!
do i = 1, 12
ida(i) = i
enddo
write(*,200) ida
200 format(12I3)
!
ic = 0
call system_clock ( t1, clock_rate, clock_max )
!
do
!
! 1) counting the number of permutations
!
ic = ic + 1
!
! 2) writing out the result:
!
! do i = 1, nmax
! write (100,"(i3,’,’)",advance = “no”) ida(i)
! enddo
! write(100,*)
!
! repeat if not being finished yet, otherwise exit.
!
if ( nextp(nmax,ida) ) then
cycle
else
exit
endif
!
enddo
!
call system_clock ( t2, clock_rate, clock_max )
dt = ( dble(t2) - dble(t1) )/ dble(clock_rate)
!
write(,) ‘Total permutations :’, ic
write(,) ‘Total time elapsed :’, dt
!
! …
!
!==
deallocate(ida)
!
stop
!==
contains
function nextp ( n, a )
logical :: nextp
integer,intent(in) :: n
integer,dimension(n),intent(inout) :: a
!
! local variables:
!
integer i,j,k,t
!
i = n-1
10 if ( a(i) .lt. a(i+1) ) goto 20
i = i-1
if ( i .eq. 0 ) goto 20
goto 10
20 j = i+1
k = n
30 t = a(j)
a(j) = a(k)
a(k) = t
j = j+1
k = k-1
if ( j .lt. k ) goto 30
j = i
if (j .ne. 0 ) goto 40
!
nextp = .false.
!
return
!
40 j = j+1
if ( a(j) .lt. a(i) ) goto 40
t = a(i)
a(i) = a(j)
a(j) = t
!
nextp = .true.
!
return
end function
end program Base12Solver
