## Combinatorial counting

Occasional Contributor
Posts: 7

# Combinatorial counting

Dear Colleagues

Many thanks for insightful discussion on my question. I am back very late but I haven been following the discussion with interest, and alongside also trying to work on my SAS question further. I think, it goes fine now. Particularly, one can compare the rannor() function with randnormal() and I feel the later one is easier to use and manipulate, even for several non-normal cases.

But, I also have another short question here, and I hope you can help me figure it out much quicker. I usually write my programs in SAS/IML, but this time I started with R and the program works fine, although R's speed for that program is painfully slow. I am writing the same thing in SAS/IML for which I need to compute all possible distinct combinations of size, say k, out of, say n, elements. Simply, I want a SAS function that does exactly what permutations() function does in R's gtools package. I have gone through LEXPERK(), ALLPERM() etc. It seems LEXPERK() is the closest option but it needs the variable list as well which I have but I want to use the list later, First, I only need to make all permutations, say permutations(10, 4) in R's function. Any idea? The other functions do not fit very well into my query - I suppose.

Many thanks and all the best

MRA

Occasional Contributor
Posts: 7

## Re: Combinatorial counting

Hi Rick

you are right, I have opened a new thread here.

I have gone through the combinatorial functions and also your old posts on this subject. It seems, only LEXPERK can do what I need, but the 'variables' option in its arguments is a problem. As, I shall use the output matrix of these, say (n, k) = (10, 4), permutations in a loop for different n's and possibly k's, it is better if I can generate it without variables option, or somehow manipulate this option to get what I need.

In any case, I am trying it in different ways to figure it out  - if possible.

Super User
Posts: 10,695

## Re: Combinatorial counting

Check GRAYCODE() of data step. of course it could be used in IML too .

Super User
Posts: 6,642

## Re: Combinatorial counting

mra,

I'm not sure if this will help or not, but I have had to tackle this sort of problem in SAS (not in SAS/IML).  This would be a piece of a DATA step:

array vars {10} var1-var10;

do a=1 to 7;

do b=a+1 to 8;

do c=b+1 to 9;

do d=c+1 to 10;

*** Code that refers to array elements a, b, c, and d;

end; end;  end; end;

You would get each combination of 4 exactly once, in the innermost loop.  Perhaps this line of thought would help in SAS/IML ?

SAS Super FREQ
Posts: 4,175

## Re: Combinatorial counting

Occasional Contributor
Posts: 7

## Re: Combinatorial counting

Hi Xia

I think Graycode() is not the solution. In fact, I feel that SAS does not offer a simple solution to this very simple problem of basic probability theory. There are many functions for combinations/permutations, but only the random ones work directly (they generate repeated combinations/permutations which I don't need; e.g. ranperm() ). It is only LEXPERK() that can solve my problem but a seemingly unnecessary argument of 'variables list' in there is an issue. The one-line R function permutations() works wonderful and the code is also running perfectly well but it is just the amount of time it takes. So, following my usual simulation policy, I have to do it in IML but then the LEXPERK() thing. I had already read Rick's older posts before I posted this message but Rick's codes don't address the all possible unique permutations question either.

/RA.

Super User
Posts: 10,695

## Re: Combinatorial counting

I am a little confused . How could you generate permutation if you miss the 'variables'  arguments in LEXPERK () .

Can you make an example to illustrate it ?

Occasional Contributor
Posts: 7

## Re: Combinatorial counting

Hi

I am not saying that I can or I did in LEXPERK() w.o. variables list. In R function permutations(), one can do it and I just need the same result as R function gives. It seems LEXPERK gives this same result but needs variable list. I tried this list as 1:n (n specified, say 10) but did not work. Following the syntax of LEXPERK(), something like lexperk(m, k, 1:n) or lexperk(m, k, x1, x2, . . ., xn) should work with if I want to generate m distinct permutations for n items taken k at a time; e.g. m = 5040 if n = 10, k = 4. In R, I only need to give n and k, but in SAS also the variables. In my case, I shall use the functions lexperk() repeatedly in a loop for many different n's, so I am trying to somehow 'manipulate' the variables option in a way that I only get the distinct permutations list, i.e. nP4, as R function gives. I hope it is relatively clear now.

All the best

Super User
Posts: 10,695

## Re: Combinatorial counting

I am not familiar with R function . Do you mean take 1 2 3 4 ...... as 'variables' argument in LEXPERK() ?

### Code: Program

`data _null_;array x[10]  (1:10);n=dim(x);k=3;nperm=perm(n,k);do j=1 to nperm+1;rc=lexperk(j, k, of x[*]);put j 5. +3 x1-x3 +3 rc=;if rc<0 then leave;end;run;`

### Log: Program

Notes (1)

1 OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;

53

54 data _null_;

55 array x[10] (1:10);

56 n=dim(x);

57 k=3;

58 nperm=perm(n,k);

59 do j=1 to nperm+1;

60 rc=lexperk(j, k, of x

• );
• 61 put j 5. +3 x1-x3 +3 rc=;

62 if rc<0 then leave;

63 end;

64 run;

1 1 2 3 rc=1

2 1 2 4 rc=3

3 1 2 5 rc=3

4 1 2 6 rc=3

5 1 2 7 rc=3

6 1 2 8 rc=3

7 1 2 9 rc=3

8 1 2 10 rc=3

9 1 3 2 rc=2

10 1 3 4 rc=3

11 1 3 5 rc=3

12 1 3 6 rc=3

13 1 3 7 rc=3

14 1 3 8 rc=3

15 1 3 9 rc=3

16 1 3 10 rc=3

17 1 4 2 rc=2

18 1 4 3 rc=3

19 1 4 5 rc=3

20 1 4 6 rc=3

21 1 4 7 rc=3

22 1 4 8 rc=3

23 1 4 9 rc=3

24 1 4 10 rc=3

25 1 5 2 rc=2

26 1 5 3 rc=3

27 1 5 4 rc=3

28 1 5 6 rc=3

29 1 5 7 rc=3

SAS Super FREQ
Posts: 4,175

## Re: Combinatorial counting

The SAS/IML language enables you to call other SAS procedures and the DATA step.  Since the LEXPERK function does what you need, the simplest solution is to call a DATA step from within your SAS/IML program.  For convenience, you can hide the call by encapsulating it within a module. The following module has the same name as the R function that you refer to. It returns the same data, although not necessarily in the same order. The call to permutations(10,4) takes 0.03 seconds on my PC.

proc iml;
/* enumerate permutations of k elements from n items,
including order. By default, the function returns
a matrix with PERM(n, k) rows. Each row is a way to
enumerate k integers from the set {1,2,...,n} */
start permutations(n, k, v=1:n);
submit n k;
data _perk;
keep x1-x&k;
array x[&n] x1-x&n;
n = &n;
k = &k;
do j = 1 to n;  x = j;  end;
nperm=perm(n, k);
do j=1 to nperm;
call lexperk(j, k, of x

• );
output;
end;
run;
endsubmit;
use _perk;
read all var _num_ into x;
close _perk;
call delete("_perk");
if IsSkipped(v) then
return( x );
y = shape( v[,x], 0, 2 );
return( y );
finish;
• /* Test 1: Return pairs of letters from {a,b,c,d} */
v = "a":"d";
g = permutations(4, 2, v);
print g;

/* Test 2: Time how long it takes to return 4-tuples from 1:10 */
t0 = time();
p = permutations(10, 4);
elapsed = time()-t0;
print (dimension(p))[c={"nrow" "ncol"}];
print elapsed;

Regular Contributor
Posts: 163

## Re: Combinatorial counting

[ Edited ]

I think you can work entirely within IML, since it is essentially a 'multiplication' of the matrix from the ALLCOMB(n, k) function, with the matrix from the ALLPERM(k) function.  Again row order is likely to be different.

``````start permutations(n, k);
c = allcomb(n, k);
p = allperm( k );
nc = nrow( c );
np = nrow( p );
a = do(0, nc # k - 1, k)` @ j(np, k) + repeat(p, nc);
return ( shape( c[a], nc # np, k) );
finish;

print (permutations( 4, 3) );``````

[Edited January 2017 - at some point part of the return statement became a link and the code was no longer rendered correctly - converted to a SAS code box to fix the problem]

SAS Super FREQ
Posts: 4,175

## Re: Combinatorial counting

Really awesome, Ian!  I tried tp combine ALLCOMB and ALLPERM, but after 30 minutes I still hadn't come up with the right formula.  I'm glad you got it to work. Your way is more efficient than mine.

Occasional Contributor
Posts: 7

## Re: Combinatorial counting

Thanks a lot. This obviously works. Particularly, Ian's code is really simple and elegant and it does exactly its job (up to the row order but that doesn't really matter - only the unique list of permutations is needed and that's what the codes gives). It helps speed up the computational burden.

thanks again.

Discussion stats
• 12 replies
• 844 views
• 1 like
• 5 in conversation