Permutations: Difference between revisions
Content added Content deleted
Line 3,567: | Line 3,567: | ||
=== Ratfor 77 === |
=== Ratfor 77 === |
||
See [[#RATFOR|RATFOR]]. |
|||
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}}== |
=={{header|FreeBASIC}}== |