8

I need to get all combinations for which the sum equal 100 using 8 variables that could take any value from 0 to 100 by incremental step of 10. (i.e. 0, 10, 20 ... 100)

The following script does just that but is very inefficient as it creates a huge dataset and I was wondering if someone had a better way of doing this. 

x <- expand.grid("ON" = seq (0,100,10), 
        "3M" = seq(0,100,10), 
        "6M" = seq(0,100,10), 
        "1Y" = seq(0,100,10), 
        "2Y" = seq(0,100,10),
        "5Y" = seq(0,100,10), 
        "10Y" = seq(0,100,10), 
        "15Y" = seq(0,100,10))

x <- x[rowSums(x)==100,]

Edit --

to answer the question from Stéphane Laurent

the result should look like

ON 3M 6M 1Y 2Y 5Y 10Y 15Y        
100 0  0  0  0  0   0   0  
 90 10  0  0  0  0   0   0  
 80 20  0  0  0  0   0   0  
 70 30  0  0  0  0   0   0  
 60 40  0  0  0  0   0   0  
 50 50  0  0  0  0   0   0

(...)

  0 0  0  0  0  0 10  90  
  0 0  0  0  0  0  0 100
989
  • 12,579
  • 5
  • 31
  • 53
ulrich
  • 3,547
  • 5
  • 35
  • 49
  • 3
    http://rosettacode.org/wiki/Count_the_coins – Roland Mar 06 '14 at 08:28
  • Is @Josh O'Brien's 'non-`expand.grid`' answer [**here**](http://stackoverflow.com/questions/20618743/creating-a-matrix-with-all-combinations-within-a-budget) relevant? – Henrik Mar 06 '14 at 08:48

3 Answers3

6

followed by Stéphane Laurent's answer, I am able to get a super fast solution by using the uniqueperm2 function here.

library(partitions)

C = t(restrictedparts(10,8))
do.call(rbind, lapply(1:nrow(C),function(i)uniqueperm2(C[i,])))

Update, there is faster solution using iterpc the package.

library(partitions)
library(iterpc)
C = t(restrictedparts(10,8))
do.call(rbind, lapply(1:nrow(C),function(i) getall(iterpc(table(C[i,]), order=T))))

It is about twice the speed of the uniqueperm2

> f <- function(){
    do.call(rbind, lapply(1:nrow(C),function(i)uniqueperm2(C[i,])))
}
> g <- function(){
    do.call(rbind, lapply(1:nrow(C),function(i) getall(iterpc(table(C[i,]), order=T))))
}
> microbenchmark(f(),g())
Unit: milliseconds
 expr      min       lq     mean   median       uq      max neval cld
  f() 36.37215 38.04941 40.43063 40.07220 42.29389 46.92574   100   b
  g() 16.77462 17.45665 19.46206 18.10101 20.65524 64.11858   100  a
Community
  • 1
  • 1
Randy Lai
  • 3,084
  • 2
  • 22
  • 23
5

Is it what you want : 

> library(partitions)
> 10*restrictedparts(10,8)

[1,] 100 90 80 70 60 50 80 70 60 50 60 50 40 40 70 60 50 40 50 40 30 40 30 60 50 40 40 30 30 20 50 40 30 30 20 40 30 20 30 20
[2,]   0 10 20 30 40 50 10 20 30 40 20 30 40 30 10 20 30 40 20 30 30 20 30 10 20 30 20 30 20 20 10 20 30 20 20 10 20 20 10 20
[3,]   0  0  0  0  0  0 10 10 10 10 20 20 20 30 10 10 10 10 20 20 30 20 20 10 10 10 20 20 20 20 10 10 10 20 20 10 10 20 10 10
[4,]   0  0  0  0  0  0  0  0  0  0  0  0  0  0 10 10 10 10 10 10 10 20 20 10 10 10 10 10 20 20 10 10 10 10 20 10 10 10 10 10
[5,]   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 10 10 10 10 10 10 20 10 10 10 10 10 10 10 10 10 10
[6,]   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 10 10 10 10 10 10 10 10 10 10
[7,]   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 10 10 10 10 10
[8,]   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 10 10
Stéphane Laurent
  • 75,186
  • 15
  • 119
  • 225
  • Not exactly please see the edit in the original question – ulrich Mar 06 '14 at 09:58
  • @user3387134 Well, if you have this result it should be easy to create all permutations. – Roland Mar 06 '14 at 16:40
  • Hey @Stephane, I'm not sure if this was available in 2014, but in the same package as `partitions` there is a function called `compositions` which returns all the possible ways to write an integer (https://en.wikipedia.org/wiki/Composition_(combinatorics)). So, calling `compositions(10, 8)` returns all 19448 results (what the OP is looking for) in about 2 milliseconds on my machine. – Joseph Wood Aug 17 '18 at 23:38
2

The partitions package includes the function compositions() that does exactly what the OP asks for.

library(partitions)

# Get 8 elements that sum up to 10
x <- compositions(n = 10, m = 8, include.zero = T)

# Convert partition to matrix
x <- as.matrix.partition(x)

# Transpose matrix
x <- t(x)

# Multiply by 10 so that elements take any value from 0 to 100 by incremental step of 10
x <- x * 10

head(x)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]  100    0    0    0    0    0    0    0
#> [2,]   90   10    0    0    0    0    0    0
#> [3,]   80   20    0    0    0    0    0    0
#> [4,]   70   30    0    0    0    0    0    0
#> [5,]   60   40    0    0    0    0    0    0
#> [6,]   50   50    0    0    0    0    0    0

tail(x)
#>          [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [19443,]    0    0   10    0    0    0    0   90
#> [19444,]    0    0    0   10    0    0    0   90
#> [19445,]    0    0    0    0   10    0    0   90
#> [19446,]    0    0    0    0    0   10    0   90
#> [19447,]    0    0    0    0    0    0   10   90
#> [19448,]    0    0    0    0    0    0    0  100

Also see answer of @Joseph Woods Finding A List of All Combinations of 6 Numbers That Add up to 10

OliRae
  • 31
  • 3