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