[R] Generating unique permutations of a vector

[Annette Heisswolf]

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