topic Re: Combinatorial counting in SAS/IML Software and Matrix Computations

Combinatorial counting

mra — Thu, 25 Jun 2015 10:29:51 GMT

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.

Since, Rick had already stated about his book which I have now and I find it very helpful.

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

Re: Combinatorial counting

mra — Thu, 25 Jun 2015 10:35:02 GMT

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.

Re: Combinatorial counting

Ksharp — Thu, 25 Jun 2015 12:15:24 GMT

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

Re: Combinatorial counting

Rick_SAS — Thu, 25 Jun 2015 13:55:20 GMT

Cross-linking to the other thread: https://communities.sas.com/message/281211#281211

Re: Combinatorial counting

mra — Thu, 02 Jul 2015 16:51:40 GMT

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.

Re: Combinatorial counting

Astounding — Thu, 02 Jul 2015 18:07:38 GMT

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 ?

Re: Combinatorial counting

Ksharp — Fri, 03 Jul 2015 13:49:43 GMT

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 ?

Re: Combinatorial counting

mra — Fri, 03 Jul 2015 14:59:33 GMT

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

Re: Combinatorial counting

Ksharp — Fri, 03 Jul 2015 15:14:10 GMT

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;

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

Re: Combinatorial counting

Rick_SAS — Mon, 06 Jul 2015 19:17:28 GMT

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;

Re: Combinatorial counting

IanWakeling — Wed, 18 Jan 2017 15:52:38 GMT

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]

Re: Combinatorial counting

Rick_SAS — Tue, 07 Jul 2015 13:56:26 GMT

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.

Re: Combinatorial counting

mra — Mon, 13 Jul 2015 11:33:56 GMT

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.