Resources

permutation

0

Hi,

is there a command to create a matrix which is all possible permutation of k elements of vector X. Basically, I am looking for an GAUSS equivalence for “perms” and “unique” commands of Matlab.

Thanks in advance!

Cheers

 

 

Tags: asked April 2, 2014

3 Answers

0
accepted

Regarding <tt>unique</tt>, GAUSS has a function called <tt>unique</tt> that returns a sorted vector with duplicates removed.

0

Thanks for this. But I guess perms has no equivalence.

0

There are currently procedures in the Time Series MT that list permutations and combinations, with and without replacement, given the number of objects and the number of “choice”.  However, none of these procedures produce the possible permutations given a vector of values.

I believe the three procedures below should allow you to create a matrix of all possible permutation of k elements of vector X. The first of these procedure most directly answers your question and will produce all possible permutations without allowing for replacement of values:

/*
**> permVec
**
** Purpose: Calculates the number of permutations without replacement
**
** Format: perms = permVec(x)
**
** Input: x - Vector n x 1, vector for permutation
**
**
** Output: perms - Matrix, list of all possible permutations of the vector x
** without replacement.
*/

proc (1) = permVec(x);
   local n,k,x2,x3,tmp,i,e;

   n = cols(X);
   k = cols(X);
   x2 = permReplaceVec(x);

   //Delete rows with duplicate value
   x3 = uniqMat(x2);
   retp(x3);
endp;

This procedure calls the two procedures other procedures, permReplaceVec and uniqMat. The first of these, perReplaceVec lists all possible permutations of a vector X allowing for replacement of values:

/*
**> permReplaceVec
**
** Purpose: Calculates the number of permutations without replacement
**
** Format: perms = permReplaceVec(x)
**
** Input: x - Vector n x 1, vector for permutation
**
**
** Output: perms - Matrix, list of all possible permutations of the vector x
** with replacement.
*/

proc (1) = permReplaceVec(x);
   local nstates, base_idx, c, r, out, base, numiters, numset, k;

   nstates = rows(x);
   k = rows(x);
   c = k;
   r = nstates^k;
   out = ones(r, c);
   base = reshape(seqa(1, 1, nstates), r, 1);

   for i(1, c-1, 1);
      numset = nstates^(k-i);
      base_idx = 1;
      for j(1, r, numset);
         out[j:(j+numset-1), i] = base[base_idx].* ones(numset,1);
         base_idx = base_idx + 1;
      endfor;
   endfor;

   //avoid last iteration of for loop for speed up
   out[., c] = base;

   //Matrix Replace
   for i(1,nstates,1);
      out = missrv(miss(out,i),x[i]);
   endfor;
retp(out);
endp;

The second procedure, uniqMat, deletes all rows from a matrix which include repeated values:

/*
**> uniqMat
**
** Purpose: Deletes rows of x which include repeated values
**
** Format: newX = uniqMat(x)
**
** Input: x - Matrix n x k, vector for permutation
**
**
** Output: newX - Matrix, includes only rows of x.
*/

proc (1) = uniqMat(x2);
   local tmp, new_X, x3,j;

   new_X = zeros(rows(X2),1);

   for i(1,rows(X2),1);
      tmp = unique(X2[i,.],1);
      if rows(tmp)!= cols(x2[i,.]);
         new_X[i,.]=i;
      endif;
   endfor;
   new_X = packr(miss(new_X,0));
   x3 = delrows(x2,new_X);
retp(x3);
endp;

Try the following code as an example:

x = rndn(4,1);
x;
x2 = permReplaceVec(x);
x2;
x3 = permVec(x);
x3;