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


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail