ALLPERM Function :: SAS/IML(R) 13.1 User's Guide

ALLPERM Function

ALLPERM (n) ;

ALLPERM (set, <, idx> ) ;

The ALLPERM function generates all permutations of a set with $n$ elements. The permutations are produced in the same order and using the same algorithm (Trotter, 1962) as the ALLPERM function in Base SAS software.

By default, the ALLPERM function returns a matrix with $n!$ rows and $n$ columns. Each row of the returned matrix represents a single permutation. The following statements generate all permutations of the set $\{ 1, 2, 3\}$ :

n = 3;
p = allperm(n);
print p;

Figure 24.36: All Permutations of Three Items

p
1	2	3
1	3	2
3	1	2
3	2	1
2	3	1
2	1	3

The first argument can be a scalar or a vector. If it is a vector, the number of elements in the vector determines the value of $n$ . The ALLPERM function can compute permutations of arbitrary numeric or character matrices. For example, the following statements compute permutations of an unsorted character vector:

a = allperm({C B A});
print a;

Figure 24.37: All Permutations of a Character Vector

a
C	B	A
C	A	B
A	C	B
A	B	C
B	A	C
B	C	A

The optional second argument, idx, can be used to control the number of rows in the output of the function. The argument must consist of consecutive integers; you cannot use it to randomly access permutations that are out of sequence. The second argument is often used to generate one or more permutations in a loop so that you do not need to allocate a huge matrix that contains all of the permutations at once. The following statements illustrate this usage:

perm = 1:n;
do i=1 to fact(n);
   perm = allperm(perm, i);
   /* do something with the i_th permutation */
end;

If you want the permutations in lexicographic order, generate the permutations and then use the SORT subroutine, as follows:

p = allperm(n);
call sort(p, 1:n);