LEXPERM Function

Generates all distinct permutations of the non-missing values of several variables in lexicographic order.

Category:

Combinatorial

Syntax

LEXPERM(count, variable-1 <, …, variable-N> )

Required Arguments

count

specifies an integer variable that ranges from 1 to the number of permutations.

variable

specifies either all numeric variables, or all character variables that have the same length. The values of these variables are permuted by LEXPERM.

Requirement

Initialize these variables before you execute the LEXPERM function.

Details

Determine the Number of Distinct Permutations

The following variables are defined for use in the equation that follows:

specifies the number of variables that are being permuted—that is, the number of arguments minus one.

specifies the number of missing values among the variables that are being permuted.

specifies the number of distinct non-missing values among the arguments.

N_i

for i=1, through i=d, N_i specifies the number of instances of the ith distinct value.

The number of distinct permutations of non-missing values of the arguments is expressed as follows:

\begin{matrix} P = \frac{(N_{1} + N_{2} + . . . + N_{d})!}{N_{1}! N_{2}! . . . N_{d}!} < = N! \end{matrix}

Note: The LEXPERM function cannot be executed with the %SYSFUNC macro.

LEXPERM Processing

Use the LEXPERM function in a loop where the argument count takes each integral value from 1 to P. You do not need to compute P provided you exit the loop when LEXPERM returns a value that is less than zero.

For 1=count<P, the following actions occur:

The argument types and lengths are checked for consistency.
The M missing values are assigned to the last M arguments.
The N-M non-missing values are assigned in ascending order to the first N-M arguments following count.
LEXPERM returns 1.

For 1<count<=P, the following actions occur:

The next distinct permutation of the non-missing values is generated in lexicographic order.
If variable-1 through variable-I did not change, but variable-J did change, where J=I+1, then LEXPERM returns J.

For count>P, LEXPERM returns –1.

If the LEXPERM function is executed with the first argument out of sequence, the results might not be useful. In particular, if you initialize the variables and then immediately execute LEXPERM with a first argument of K, you will not get the Kth permutation (except when K is 1). To get the Kth permutation, you must execute LEXPERM K times, with the first argument accepting values from 1 through K in that exact order.

Comparisons

SAS provides three functions or CALL routines for generating all permutations:

ALLPERM generates all possible permutations of the values, missing or non-missing, of several variables. Each permutation is formed from the previous permutation by interchanging two consecutive values.
LEXPERM generates all distinct permutations of the non-missing values of several variables. The permutations are generated in lexicographic order.
LEXPERK generates all distinct permutations of K of the non-missing values of N variables. The permutations are generated in lexicographic order.

ALLPERM is the fastest of these functions and CALL routines. LEXPERK is the slowest.

Example

The following is an example of the LEXPERM function.

data _null_;
   array x[6] $1 ('X' 'Y' 'Z' ' ' 'Z' 'Y');
   nfact=fact(dim(x));
   put +3 nfact=;
   do i=1 to nfact;
      rc=lexperm(i, of x[*]);
      put i 5. +2 rc= +2 x[*];
      if rc<0 then leave;
   end;
run;

SAS writes the following output to the log:

   nfact=720
    1  rc=1   X Y Y Z Z  
    2  rc=3   X Y Z Y Z  
    3  rc=4   X Y Z Z Y  
    4  rc=2   X Z Y Y Z  
    5  rc=4   X Z Y Z Y  
    6  rc=3   X Z Z Y Y  
    7  rc=1   Y X Y Z Z  
    8  rc=3   Y X Z Y Z  
    9  rc=4   Y X Z Z Y  
   10  rc=2   Y Y X Z Z  
   11  rc=3   Y Y Z X Z  
   12  rc=4   Y Y Z Z X  
   13  rc=2   Y Z X Y Z  
   14  rc=4   Y Z X Z Y  
   15  rc=3   Y Z Y X Z  
   16  rc=4   Y Z Y Z X  
   17  rc=3   Y Z Z X Y  
   18  rc=4   Y Z Z Y X  
   19  rc=1   Z X Y Y Z  
   20  rc=4   Z X Y Z Y  
   21  rc=3   Z X Z Y Y  
   22  rc=2   Z Y X Y Z  
   23  rc=4   Z Y X Z Y  
   24  rc=3   Z Y Y X Z  
   25  rc=4   Z Y Y Z X  
   26  rc=3   Z Y Z X Y  
   27  rc=4   Z Y Z Y X  
   28  rc=2   Z Z X Y Y  
   29  rc=3   Z Z Y X Y  
   30  rc=4   Z Z Y Y X  
   31  rc=-1   Z Z Y Y X