Generation of permutation sequences

Generation of permutation sequences

PROBLEM

Let N denote an integer such that N>=2. The problem is how to generate all the FACT(N) permutations of a set {1,...,N}.

Note:

FACT is the factorial

IMPLEMENTATION

Unit: internal subroutine

Parameters: integer N>=2

Result: subroutine displays on the screen all permutation sequences

PERMUTATION: procedure
parse arg N
C. = 1; Pr. = 1
do J = 1 to N; P.J = J; end
C.N = 0
say DISPLAY(N)
J = 1
do while J < N
  X = 0
  do J = 1 while C.J = N - J + 1
    Pr.J = \Pr.J; C.J = 1
    if Pr.J then X = X + 1
  end
  if J < N
    then do
      if Pr.J then K = C.J + X
              else K = N - J + 1 - C.J + X
      Kp1 = K + 1; W = P.K
      P.K = P.Kp1; P.Kp1 = W
      say DISPLAY(N)
      C.J = C.J + 1
    end
end
return

DISPLAY: procedure expose P.
parse arg N
Permutation = P.N
do J = N - 1 to 1 by -1
  Permutation = P.J Permutation
end
return Permutation

EXAMPLE

N = 3; call PERMUTATION N
exit
PERMUTATION: procedure
...

displays on the screen:

1 2 3
2 1 3
2 3 1
3 2 1
3 1 2
1 3 2

Further example
See Test Data Sets

CONNECTIONS

Random Permutation
Generation of all subsets with K elements
Number of combinations

Literature
Lipski W. Kombinatoryka dla Programistow

Wydawnictwa Naukowo-techniczne, Warszawa, 1982