[R] Generating unique permutations of a vector

[Robin Hankin]

Annette

I understand your problem.

I think you may find 'blockparts(rep(5,5),5)' helpful.

I'm working on permutations of multisets right now
and expect to have functionality in partitions package
as soon as I finish the Other Ten Thousand Things
On My Things To Do List.arts

Perhaps we could talk offline.

best wishes


Robin




Annette Heisswolf wrote:
> 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
>


-- 
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877