ALLCOMB Function

ALLCOMB (n, k) ;

ALLCOMB (n, comb, <, idx> ) ;

The ALLCOMB function generates all combinations of k elements taken from a set of n numerical indices. The combinations are produced in the same order and using the same algorithm (Nijenhuis and Wilf, 1978) as the ALLCOMBI function in Base SAS software. In particular, the function returns indices in the range 1–n, and each combination is in sorted order.

By default, the ALLCOMB function returns a matrix with ${n \choose k}$ rows and k columns. Each row of the returned matrix represents a single combination. The following statements generate all combinations of two elements from the set $\{ 1, 2, 3, 4\} $:

n = 4; /* used throughout this example */
k = 2; /* used throughout this example */
c = allcomb(n, k); 
print c;

Figure 23.34: All Pairwise Combinations of Four Items

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


The second argument can be a scalar or a vector. If it is a vector, it must contain a valid combination of the set $\{ 1,2,\ldots ,n\} $. (To be valid, the comb elements must be in increasing order.) The number of elements in the vector determines the value of $k$. For example, the following statements generate all combinations of length two from a set with four elements, beginning with the third combination that is shown in Figure 23.34:

d = allcomb(4, {1 3}); 

To obtain all combinations in order, initialize the comb argument to 1:k or to the zero vector with $k$ elements.

The optional third argument, idx, controls the number of rows in the output of the function. If you specify idx, then the sequence is initialized with the comb argument and the first row of the output is the combination that occurs after the comb argument. For example, the following statements generate five pairwise combinations, beginning after the third combination shown in Figure 23.34:

e = allcomb(n, {1 3}, 1:5); 

The idx argument must consist of consecutive integers; you cannot use it to randomly access combinations that are out of sequence. The idx argument is often used to generate one or more combinations in a loop so that you do not need to allocate a huge matrix that contains all of the combinations at once. The following statements illustrate this usage. Notice that you should initialize the comb argument to the zero vector if you want the first result to be the combination 1:k.

ncomb = comb(n, k);
comb = j(1, k, 0);
do i=1 to ncomb;
   comb = allcomb(n, comb, i);
   /* do something with the i_th combination */
end;

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

c = allcomb(n, k); 
call sort(c, 1:k);