Filtering permutations to avoid running out of memory

Question

The context of this problem is asset allocation. If I have N assets, and can allocate them in 5% chunks, what are the permutations that exist such that the sum of the allocation is exactly equal to 100%.

For example if I had 2 assets there would be 21 (created using my function "fMakeAllocationsWeb(2)" code at the bottom of this post:

      [,1] [,2]
 [1,]    0  100
 [2,]    5   95
 [3,]   10   90
 [4,]   15   85
 [5,]   20   80
 [6,]   25   75
 [7,]   30   70
 [8,]   35   65
 [9,]   40   60
[10,]   45   55
[11,]   50   50
[12,]   55   45
[13,]   60   40
[14,]   65   35
[15,]   70   30
[16,]   75   25
[17,]   80   20
[18,]   85   15
[19,]   90   10
[20,]   95    5
[21,]  100    0

The problem of course come when the number of assets increases, even modestly. This is understandable as with repetition the number of permutations is n^(n) and I'm not able to allocate the intermediate step of creating all permutations to memory. For example with 20 assets the number of permutations is 5.84258701838598E+27!!

I would like to be able to filter these on the fly (sum==100) so as to not run into the memory allocation issue. Digging into the code beneath gtools::permutations it seems to be vectorised and intervening there to filter seems impossible.

Would gratefully welcome any thoughts - ideally would prefer to stick with R code and packages.

Many thanks

Russ

installifMissing <- function(sPackageName) {
  if (!sPackageName %in% installed.packages()) install.packages(sPackageName)
}


fMakeAllocationsWeb<-function(iNumAssets=10,iIncrement=5){
installifMissing("gtools")
require(gtools)

iAlloc<-seq(0,100,by=iIncrement) #'the allocation increments eg 0,5,10...,95,100
#'generate permutations
permut<-permutations(n=length(iAlloc),r=iNumAssets,v=iAlloc,repeats.allowed=TRUE)
#'filter permuatations for those which sum to exactly 100'
permutSum<-apply(permut,MARGIN=1,FUN=sum)
permut100<-permut[which(permutSum==100),]
return(permut100)
}

Answer 1

If you install the partitions package, you have the restrictedparts function that will enumerate all the ways you can add n numbers together to get a sum S. In your case, you want to restrict the summands to be multiples of 5, and the restriction is to add up to S=100. Instead, divide your summands by 5 and have the total add up to 20. If you want 2 assets, then the code restrictedparts(100/5,2) * 5 will give you the 10 unordered pairs.

You can then loop through the columns and enumerate, for each, the set of all permutations of asset allocations. You'll have to deal carefully with the case where there are repeated elements - for example, we generate {100,0} which represents <100,0> and <0,100> whereas {50,50} only represents the single allocation <50,50>. You can deal with this by using the set attribute of permuatations

restrictedparts(100/5,20) * 5 gives 627 partitions that add up to 100% - and you'll need to permute each of these to get your full list of allocations.

Answer 2

In your problem, you will still have large number of combinations to deal with even after filtering.

Your problem essentially boils down to n multichoose k problem as described here You want to choose k=20 slots of 5% weightage each to allocate from n assets.

So in your example case of 20 assets, your number of combinations would still be

choose(39, 20)
## [1] 68923264410

I suggest you have a look at DEoptim package which has specific examples directly related to your problem at hand. It uses differential evolution.