A RandomPerm.T (hereinafter a permutation) represents a pseudo-random permutation of a finite set of integers [0..n-1], that is a bijective (one-one and onto) map from the set [0..n-1] to itself.

Formally, a permutation p has the components:

       size(p)  a nonnegative integer
       perm(p)  a permutation of the integers [0..size(p)-1]
       index(p) an integer in the range [0..size(p)]

INTERFACE RandomPerm;

IMPORT Random;

EXCEPTION Exhausted;

TYPE
  T = OBJECT
      METHODS
        size (): CARDINAL;
        (* Returns "size(p)", the number of elements in the permutation. *)

        index (): CARDINAL;
        (* Returns "index(p)", the index of the next element in the
           permutation. *)

        copy (): T;
        (* Returns a new permutation "q" with:

|  size(q)  = size(p)
|  perm(q)  = perm(p)
|  index(q) = index(p)

           and the same allocation type as p. *)

        next (): CARDINAL RAISES {Exhausted};
        (* Returns the next element of the permutation "p".  "next(p)" is
           equivalent to:

|   IF index(p)=size(p) THEN
|     index(p) := 0; RAISE Exhausted
|   END;
|   WITH n = perm(p)(index(p)) DO
|     index(p) := index(p)+1;
|     RETURN n
|   END

           *)
      END;

TYPE
  LowQuality <:
    T OBJECT METHODS init (n: CARDINAL; r: Random.T): LowQuality; END;

  HighQuality <:
    T OBJECT METHODS init (n: CARDINAL; r: Random.T): HighQuality; END;

HighQuality permutations use Algorithm 3.4.2P of Knuth's {\it Seminumerical Algorithms} (second edition), and thus require space O(n). LowQuality permutations are not really very random but use constant space and work for n up to 2^(BITSIZE(INTEGER)-2)-1.

PROCEDURE Fill(VAR(*OUT*) perm: ARRAY OF CARDINAL; r: Random.T);

Fill perm with a new high quality permutation of the integers [0..NUMBER(perm)-1].

END RandomPerm.