CODEWITHSUNDEEP
rmathcombinations
RobinvG
RobinvG

Reputation: 73

All possible ways to split n over k groups - R

I am stuck in a mathematical problem. I would like to make a function that outputs all the ways an integer "n" can be divide into "k" groups in such a way that in each group "k" is at least 1 (k >= 1).

The function could look something like: 

n_ways <- function(n,k) {...}

I would like a dataFrame as an output. So for: n_ways(5,3)

     A  B  C
1    3  1  1
2    1  3  1
3    1  1  3
4    2  2  1
5    2  1  2
6    1  2  2

The order in which the solutions are presented in the dataFrame is not important.

I looked for solutions like here and in other languages like here and here. Unfortunately I am not that good to make a function that suits my problem based on this, but hopefully you are.

Thanks a lot in advance!

Upvotes: 4

Views: 786

Answers (3)

cryo111
cryo111

Reputation: 4474

You can use the partitions package:

library(partitions)
t(compositions(5, 3, FALSE))
#[1,] 3 1 1
#[2,] 2 2 1
#[3,] 1 3 1
#[4,] 2 1 2
#[5,] 1 2 2
#[6,] 1 1 3

From the respective help file

Function compositions() returns all 2^(n-1) ways of partitioning an integer; thus 4 + 1 + 1 is distinct from 1 + 4 + 1 or 1 + 1 + 4.

Upvotes: 6

J_F
J_F

Reputation: 10372

Here is my solution, it is not very fast, but it could be a starting point for you to improve the speed.

n_ways <- function(n, k){

    addend <- rep(seq(1,n),k)

    combinations <- combn(x = addend, m = k)

    combinations <- t(combinations[,which(colSums(combinations) == n)])

    return(unique(combinations))
}

n_ways(5,3)

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

If you are interested in, I can write some comments to the function, but it consists of R base functions as colSums or combn.

Upvotes: 4

csgillespie
csgillespie

Reputation: 60492

Two possibilities:

eg <- expand.grid(rep(list(1:5), 3))
unique(eg[which(rowSums(eg)==5),])

which results in:

   Var1 Var2 Var3
3     3    1    1
7     2    2    1
11    1    3    1
27    2    1    2
31    1    2    2
51    1    1    3

Or use the combinat (but this samples without replacement)

library(combinat)
combn(5, 3)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    1    1    1    2    2    2     3
# [2,]    2    2    2    3    3    4    3    3    4     4
# [3,]    3    4    5    4    5    5    4    5    5     5

Upvotes: 4

Related Questions