[R] Generating unique permutations of a vector

From: Annette Heisswolf <annette.heisswolf_at_utu.fi>
Date: Fri, 14 Nov 2008 10:35:21 +0200


Hi all,

I try to generate sets of strategies that contain probability distributions for a defined number of elements, e.g. imagine an animal that can produce 5 different types of offspring and I want to figure out which percentage of each type it should produce in order to maximize its fitness. In order to do so, I need to calculate the fitness for all potential strategies. As an example, if I assume the probability levels to be 0, 0.2, 0.4, 0.6, 0.8, 1, I can generate all possible probability distributions for the 5 types of offspring by using the following R-code:

library(partitions)
library(crank)

n=5
P=parts(n)
L=length(P[1,])

for (i in 1:L){

   ma=unique(permute(P[,i]))
   if (i==1) m=ma else m=rbind(m,ma)
}
m=m/n

> m

        [,1] [,2] [,3] [,4] [,5]

   [1,]  1.0  0.0  0.0  0.0  0.0
   [2,]  0.0  1.0  0.0  0.0  0.0
   [3,]  0.0  0.0  1.0  0.0  0.0
   [4,]  0.0  0.0  0.0  1.0  0.0
   [5,]  0.0  0.0  0.0  0.0  1.0
   [6,]  0.8  0.2  0.0  0.0  0.0
   [7,]  0.8  0.0  0.2  0.0  0.0
   [8,]  0.8  0.0  0.0  0.2  0.0
   [9,]  0.8  0.0  0.0  0.0  0.2
  [10,]  0.2  0.8  0.0  0.0  0.0
  [11,]  0.2  0.0  0.8  0.0  0.0
  [12,]  0.2  0.0  0.0  0.8  0.0
  [13,]  0.2  0.0  0.0  0.0  0.8
  [14,]  0.0  0.8  0.2  0.0  0.0
  [15,]  0.0  0.8  0.0  0.2  0.0
  [16,]  0.0  0.8  0.0  0.0  0.2
  [17,]  0.0  0.2  0.8  0.0  0.0
  [18,]  0.0  0.2  0.0  0.8  0.0
  [19,]  0.0  0.2  0.0  0.0  0.8
  [20,]  0.0  0.0  0.8  0.2  0.0
  [21,]  0.0  0.0  0.8  0.0  0.2
  [22,]  0.0  0.0  0.2  0.8  0.0
  [23,]  0.0  0.0  0.2  0.0  0.8
  [24,]  0.0  0.0  0.0  0.8  0.2
  [25,]  0.0  0.0  0.0  0.2  0.8

  [26,] 0.6 0.4 0.0 0.0 0.0
  [27,] 0.6 0.0 0.4 0.0 0.0
.
.
.

[106,] 0.4 0.2 0.2 0.2 0.0
[107,] 0.4 0.2 0.2 0.0 0.2
[108,] 0.4 0.2 0.0 0.2 0.2
[109,] 0.4 0.0 0.2 0.2 0.2
[110,] 0.2 0.4 0.2 0.2 0.0
[111,] 0.2 0.4 0.2 0.0 0.2
[112,] 0.2 0.4 0.0 0.2 0.2
[113,] 0.2 0.2 0.4 0.2 0.0
[114,] 0.2 0.2 0.4 0.0 0.2
[115,] 0.2 0.2 0.2 0.4 0.0
[116,] 0.2 0.2 0.2 0.0 0.4
[117,] 0.2 0.2 0.0 0.4 0.2
[118,] 0.2 0.2 0.0 0.2 0.4
[119,] 0.2 0.0 0.4 0.2 0.2
[120,] 0.2 0.0 0.2 0.4 0.2
[121,] 0.2 0.0 0.2 0.2 0.4
[122,] 0.0 0.4 0.2 0.2 0.2
[123,] 0.0 0.2 0.4 0.2 0.2
[124,] 0.0 0.2 0.2 0.4 0.2
[125,] 0.0 0.2 0.2 0.2 0.4
[126,] 0.2 0.2 0.2 0.2 0.2

Using the "unique()" function is necessary, as the "permute()" function doesn't check whether some elements within the vector to be permuted are identical, e.g. permute(c(1,0,0)) gives:

      [,1] [,2] [,3]
[1,] 1 0 0
[2,] 1 0 0
[3,] 0 1 0
[4,] 0 0 1
[5,] 0 1 0
[6,] 0 0 1

In my above example, this means that permuting the first column of P,

> P[,1]
[1] 5 0 0 0 0

gives 5! = 120 permutations, although there are in fact only 5 unique ones, namely:

5 0 0 0 0
0 5 0 0 0
0 0 5 0 0
0 0 0 5 0
0 0 0 0 5

On my computer (Windows XP SP3, Pentium(R) 4 CPU 2.40GHz, 504 MB RAM - but I've also tried it on another computer with 1 GB RAM) this leads to the problem that as soon as the vector to be permuted has more than 9 elements, the resulting matrix get's too big and R won't execute the permutation.

Thus, even when I aim to reduce the total number of unique permutations, e.g. by using less probability levels than there are elements, the above   code doesn't work. For instance, I've used 10 elements but only the probability levels 0, 0.2, 0.4, 0.6, 0.8, 1 as above, thus, P looks like this:

> P

       [,1] [,2] [,3] [,4] [,5] [,6] [,7]

  [1,]    5    4    3    3    2    2    1
  [2,]    0    1    2    1    2    1    1
  [3,]    0    0    0    1    1    1    1
  [4,]    0    0    0    0    0    1    1
  [5,]    0    0    0    0    0    0    1
  [6,]    0    0    0    0    0    0    0
  [7,]    0    0    0    0    0    0    0
  [8,]    0    0    0    0    0    0    0
  [9,]    0    0    0    0    0    0    0

[10,] 0 0 0 0 0 0 0

In this case, permute(P[,1]) would give 10! = 3 628 800 permutations, although there are only 10 unique ones. There are more then 10 unique permutations for the other columns, but still their numbers should be small enough.

Thus: Has anyone been working on a similar problem and found a better way to generate such probability distributions? I'd appreciate any kind of hint how to solve my problem. Thanks!

Annette

-- 
Annette Heisswolf
Section of Ecology
Department of Biology
University of Turku
20014 Turku, Finland

______________________________________________
R-help_at_r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Received on Fri 14 Nov 2008 - 08:38:22 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Fri 14 Nov 2008 - 10:30:26 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive