Permutations: Difference between revisions
→Fortran 77
Walterpachl (talk | contribs) m (teag correction) |
|||
Line 3,516:
nextp=.true.
end</lang>
=== Ratfor 77 ===
For translation to FORTRAN 77 with the public domain ratfor77 preprocessor.
<lang ratfor># Heap’s algorithm for generating permutations. Algorithm 2 in
# Robert Sedgewick, 1977. Permutation generation methods. ACM
# Comput. Surv. 9, 2 (June 1977), 137-164.
define(n, 3)
define(n_minus_1, 2)
implicit none
integer a(1:n)
integer c(1:n)
integer i, k
integer tmp
10000 format ('(', I1, n_minus_1(' ', I1), ')')
# Initialize the data to be permuted.
do i = 1, n {
a(i) = i
}
# What follows is a non-recursive Heap’s algorithm as presented by
# Sedgewick. Sedgewick neglects to fully initialize c, so I have
# corrected for that. Also I compute k without branching, by instead
# doing a little arithmetic.
do i = 1, n {
c(i) = 1
}
i = 2
write (*, 10000) a
while (i <= n) {
if (c(i) < i) {
k = mod (i, 2) + ((1 - mod (i, 2)) * c(i))
tmp = a(i)
a(i) = a(k)
a(k) = tmp
c(i) = c(i) + 1
i = 2
write (*, 10000) a
} else {
c(i) = 1
i = i + 1
}
}
end</lang>
Here is what the generated FORTRAN 77 code looks like:
<lang fortran>C Output from Public domain Ratfor, version 1.0
implicit none
integer a(1: 3)
integer c(1: 3)
integer i, k
integer tmp
10000 format ('(', i1, 2(' ', i1), ')')
do23000 i = 1, 3
a(i) = i
23000 continue
23001 continue
do23002 i = 1, 3
c(i) = 1
23002 continue
23003 continue
i = 2
write (*, 10000) a
23004 if(i .le. 3)then
if(c(i) .lt. i)then
k = mod (i, 2) + ((1 - mod (i, 2)) * c(i))
tmp = a(i)
a(i) = a(k)
a(k) = tmp
c(i) = c(i) + 1
i = 2
write (*, 10000) a
else
c(i) = 1
i = i + 1
endif
goto 23004
endif
23005 continue
end</lang>
{{out}}
$ ratfor77 permutations.r > permutations.f && f2c permutations.f && cc -o permutations permutations.c -lf2c && ./permutations
<pre>(1 2 3)
(2 1 3)
(3 1 2)
(1 3 2)
(2 3 1)
(3 2 1)</pre>
=={{header|FreeBASIC}}==
| |||