Statistical programming, matrix languages, and more

Permutation of row vectors

Accepted Solution Solved
Reply
Occasional Contributor
Posts: 13
Accepted Solution

Permutation of row vectors

Happy New Year all!

I am working on a permutation test but I am stuck on obtaining all the possible permutations. I am using proc iml and what I want to do is to obtain individual data sets for each possible swapping of two rows in a matrix. I supplied a sample data set and the code I am using below. Currently, this proc iml SAS code is rearranging multiple rows so the first problem is to adjust it so only two rows are swapped at a time. The second problem is to repeat the procedure for every possible unique row permutation (without resampling). For example, this data set would have 10 different "b" data sets produced for the 10 possible ways two rows can be swapped. Let me know if further explanation is needed. I am open to other methods but so far I have found proc iml to be the most useful. Thanks!!

data ys;

  do i = 1 to 10;

  call streaminit(123);

  u1 = rand("Uniform");

  y_12 = ceil(5*u1);

  call streaminit(456);

  u2 = rand("Uniform");

  y_13 = ceil(5*u2);

  call streaminit(789);

  u3 = rand("Uniform");

  y_23 = ceil(5*u3);

  output;

  end;

drop u1 u2 u3 i;

run;

/* permutation test */

/*this works but it currently swaps more than two rows. I need to edit so only two rows are swapped at a time = single permutation*/

/*Source: http://blogs.sas.com/content/iml/2010/10/06/generating-random-permutations/*/


proc iml;

/** generate one random permutation with N>0 elements **/

start RandPerm(N);

   u = 1:N;                    /** allocate u **/

   call randgen(u, "Uniform"); /** fill with random numbers **/

   return(rank(u));            /** return rank (order) of elements **/

finish;

/** call the permutation module **/

call randseed(123);      /** optional: make numbers reproducible **/

p = RandPerm(10);

print p;

/** Module to permute the rows of a matrix **/

start PermuteRows(M);

   n = nrow(M);          /** how many rows? **/

   r = RandPerm(n);      /** get a random permutation **/

   return ( M[r,] );     /** return matrix with permuted rows **/

finish;

/** test the module **/

use ys;

read all var {y_12 y_13 y_23} into a;

b = PermuteRows(a);

print a;

print b;

Here is the current output:

                                          a

                                         3         1         1

                                         2         2         2

                                         2         1         1

                                         1         5         2

                                         3         5         4

                                         5         2         5

                                         1         3         5

                                         1         1         1

                                         4         4         5

                                         4         3         5

                                               b

                                         4         4         5

                                         2         2         2

                                         3         5         4

                                         4         3         5

                                         5         2         5

                                         1         1         1

                                         2         1         1

                                         1         3         5

                                         3         1         1

                                         1         5         2

Here is an example of the desired output (notice only two rows are swapped here: row 3 & row 9). Then, the next step is to repeat the procedure to create data sets for each possible row exchange.

                                          a

                                         3         1         1

                                         2         2         2

                                         2         1         1

                                         1         5         2

                                         3         5         4

                                         5         2         5

                                         1         3         5

                                         1         1         1

                                         4         4         5

                                         4         3         5

                                           

                                             b             

                                         3         1         1

                                         2         2         2

                                         4         4         5

                                         1         5         2

                                         3         5         4

                                         5         2         5

                                         1         3         5

                                         1         1         1

                                         2         1         1

                                         4         3         5


Accepted Solutions
Solution
‎01-04-2013 09:27 AM
SAS Super FREQ
Posts: 3,620

Re: Permutation of row vectors

There are "n choose 2" (= n(n-1)/2) ways to permute n rows. Your example of 10 rows actually has 45 permutations, not 10. You can permute row 1 with any of rows 2-10, permute row 2 with any of rows 3-10, and so forth.

You can use the SAS/IML ALLCOMB function to generate all pairwise combinations of the rows. Then you just have to loop over all pairwise combinations, and swap the appropriate rows:

start ReverseRowVector( v ); /* helper function */
   return( v[ ,ncol(v):1] );
finish;

/* given matrix a and row vector {i j}, return a with
   rows i and j swapped */
start SwapRowPairs(rows, a);
   b = a;
   b[rows, ] = a[ReverseRowVector(rows), ];
   return( b );
finish;

/* test it */
c = allcomb(nrow(a), 2);
b = SwapRowPairs(c[1,], a);
print (c[1,]) a b;

/* use it */
result = j(nrow(c), 1);
do i = 1 to nrow(c);
   b = SwapRowPairs(c[i,], a);
   /* compute result for this permutation. Store in result */
end;

For more on implementing permutation tests in SAS/IML, see p. 11-13 of http://support.sas.com/resources/papers/proceedings10/329-2010.pdf

View solution in original post


All Replies
Solution
‎01-04-2013 09:27 AM
SAS Super FREQ
Posts: 3,620

Re: Permutation of row vectors

There are "n choose 2" (= n(n-1)/2) ways to permute n rows. Your example of 10 rows actually has 45 permutations, not 10. You can permute row 1 with any of rows 2-10, permute row 2 with any of rows 3-10, and so forth.

You can use the SAS/IML ALLCOMB function to generate all pairwise combinations of the rows. Then you just have to loop over all pairwise combinations, and swap the appropriate rows:

start ReverseRowVector( v ); /* helper function */
   return( v[ ,ncol(v):1] );
finish;

/* given matrix a and row vector {i j}, return a with
   rows i and j swapped */
start SwapRowPairs(rows, a);
   b = a;
   b[rows, ] = a[ReverseRowVector(rows), ];
   return( b );
finish;

/* test it */
c = allcomb(nrow(a), 2);
b = SwapRowPairs(c[1,], a);
print (c[1,]) a b;

/* use it */
result = j(nrow(c), 1);
do i = 1 to nrow(c);
   b = SwapRowPairs(c[i,], a);
   /* compute result for this permutation. Store in result */
end;

For more on implementing permutation tests in SAS/IML, see p. 11-13 of http://support.sas.com/resources/papers/proceedings10/329-2010.pdf

Occasional Contributor
Posts: 13

Re: Permutation of row vectors

Hey Rick,

Thanks so much for the help. I tried to apply it and run in SAS but I got the following error message "Error: Not enough arguments for function ALLCOMB." I checked the user guide you referenced but I don't see the issue. What am I missing?

This is the code I was running:

data ys;

  do i = 1 to 10;

  call streaminit(123);

  u1 = rand("Uniform");

  y_12 = ceil(5*u1);

  call streaminit(456);

  u2 = rand("Uniform");

  y_13 = ceil(5*u2);

  call streaminit(789);

  u3 = rand("Uniform");

  y_23 = ceil(5*u3);

  output;

  end;

drop u1 u2 u3 i;

run;

proc iml;

use ys;

read all var {y_12 y_13 y_23} into a;

print a;

start ReverseRowVector( v ); /* helper function */

   return( v[ ,ncol(v):1] );

finish;

/* given matrix a and row vector {i j}, return a with

   rows i and j swapped */

start SwapRowPairs(rows, a);

   b = a;

   b[rows, ] = a[ReverseRowVector(rows), ];

   return( b );

finish;

/* test it */

c = allcomb(nrow(a), 2);

b = SwapRowPairs(c[1,], a);

print (c[1,]) a b;

/* use it */

result = j(nrow(c), 1);

do i = 1 to nrow(c);

   b = SwapRowPairs(c[i,], a);

   /* compute result for this permutation. Store in result */

end;

SAS Super FREQ
Posts: 3,620

Re: Permutation of row vectors

I assume this means that you are not running SAS 9.3.  The ALLCOMB function was added in SAS/IML 9.3.

You can create the set of all combinations in the DATA step and then read in the c matrix from that data set.  Use the ALLCOMBI function in the DATA step to generate the set of all combinations.

SAS Super FREQ
Posts: 3,620

Re: Permutation of row vectors

Incidentally, you only need to make one call to call streaminit(123) outside of the loop. The other calls don't do anything.

Random number seeds: Only the first seed matters! - The DO Loop

🔒 This topic is solved and locked.

Need further help from the community? Please ask a new question.

Discussion stats
  • 4 replies
  • 1068 views
  • 3 likes
  • 2 in conversation