Permutations: Difference between revisions

==={{Header|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>