Permutation Generator

by Stephen R. Schmitt

Definition

A permutation is the rearrangement of the items in a list. That is, order matters. The number of permutations for a set of N items is N! (N factorial). For example, there are 2 permutations of {1, 2} and 6 permutations of {1, 2, 3}. As N increased, it becomes very difficult to enumerate all the possible permutations.

Note: A factorial is written using an exclamation point - 5 factorial is written 5! - it is equivalent to 5·4·3·2·1.

Zeno source code

Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy to learn and is suitable for educational purposes.

• Download Page

const num : int := 4
var a : array[num] of int
var pos : int

program

    var i : int

    pos := -1
    for i := 2...num do 
        a[i] := 0
    end for

    permute( 1 )

end program

% arrange global array a in all possible ways
procedure permute( n : int )

    var i : int

    incr pos
    a[n] := pos
    
    if pos = num then 
        show_array
    else
        for i := 1...num do
            if a[i] = 0 then 
                permute( i )
            end if
        end for
    end if
   
    decr pos
    a[n] := 0

end procedure

% display contents of global array a 
procedure show_array

    var i, j : int

    for i := 1...num do 
        put a[i]:3...
    end for
    put ""
   
end procedure

Sample output

  1  2  3  4 
  1  2  4  3 
  1  3  2  4 
  1  4  2  3 
  1  3  4  2 
  1  4  3  2 
  2  1  3  4 
  2  1  4  3 
  3  1  2  4 
  4  1  2  3 
  3  1  4  2 
  4  1  3  2 
  2  3  1  4 
  2  4  1  3 
  3  2  1  4 
  4  2  1  3 
  3  4  1  2 
  4  3  1  2 
  2  3  4  1 
  2  4  3  1 
  3  2  4  1 
  4  2  3  1 
  3  4  2  1 
  4  3  2  1 

AbCd Classics - free on-line books