Statistical programming, matrix languages, and more

Combinatorial counting

Reply
Occasional Contributor mra
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.

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

Occasional Contributor 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.

Grand Advisor
Posts: 9,571

Re: Combinatorial counting

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

Respected Advisor
Posts: 4,959

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: 3,406

Re: Combinatorial counting

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

Occasional Contributor mra
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.

Grand Advisor
Posts: 9,571

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 mra
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

Grand Advisor
Posts: 9,571

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: 3,406

    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;

    Frequent Contributor
    Posts: 130

    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: 3,406

    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 mra
    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.

    Ask a Question
    Discussion stats
    • 12 replies
    • 802 views
    • 1 like
    • 5 in conversation