Randomly partition an integer into n parts, with zero a possible outcome

Question

How do I randomly partition an integer into n parts, with zero a possible outcome? (Preferably in R)

For example, to partition the integer number 5 into 3 parts and do this 4 times, I might get this output:

Thanks!

Are you just looking for `sample(x, size, replace)`? This randomly draws `size` elements from `x`. `sample(0:5, 3, TRUE)`. To do this 4 times, use `replicate(4, sample(0:5, 3, TRUE))` (or just draw 4*3=12 elements and split the vector into 4 parts). — CL., Jul 13 '15 at 14:46
Not quite.. I had looked at the sample() function before, but I don't think it's doing what I need. I want the sum of all elements of the partition to be a given number (5, in my example) , and randomly generate these partitions. One way might be to write out all possible partitions, and then use a random number generator to choose a partition. However, the number of possible partitions gets very large for large integers, and this might be a problem. — VeBeKay, Jul 13 '15 at 14:58
And what is the difference between what it does and what you need? Maybe you can clarify the question a little. — CL., Jul 13 '15 at 15:00
`expand.grid(0:5, 0:5,0:5)[rowSums(expand.grid(0:5, 0:5,0:5))==5, ]` will give you the all possible triplets adds up to 5. You can now use `sample`. — Khashaa, Jul 13 '15 at 15:07

score 5 · Answer 1 · answered Jul 13 '15 at 15:12

5

library(partitions)
t(restrictedparts(5, 3))
[1,] 5 0 0
[2,] 4 1 0
[3,] 3 2 0
[4,] 3 1 1
[5,] 2 2 1

There are other helpful functions in that package. This document will walk through random sampling and combinatorials link here.

answered Jul 13 '15 at 15:12

Pierre L

28,203
6
47
69

jblood94 · Answer 2 · 2023-08-23T13:33:13.470

Take a look at RcppAlgos::compositionsSample:

RcppAlgos::compositionsSample(0:5, 3, repetition = TRUE, weak = TRUE, 
    n = 10)
#>       [,1] [,2] [,3]
#>  [1,]    2    0    3
#>  [2,]    4    1    0
#>  [3,]    1    0    4
#>  [4,]    1    1    3
#>  [5,]    3    2    0
#>  [6,]    1    2    2
#>  [7,]    0    3    2
#>  [8,]    3    0    2
#>  [9,]    0    5    0
#> [10,]    0    1    4

Original Answer

To generate a random k-partition of integer m (with zeros allowed), take k-1 random uniform samples of 0:m, sort them, prepend 0, then append m, then take the differences. For m = 5, k = 3:

diff(c(0, sort(sample(0:5, 2, 1)), 5))
#> [1] 1 0 4

A function to return multiple random partitions:

library(Rfast)

rpart <- function(n, m, k) {
  coldiffs(cbind(0, rowSort(matrix(sample(0:m, n*(k - 1), 1), n)), m))
}

rpart(10, 5, 3)
#>       [,1] [,2] [,3]
#>  [1,]    4    1    0
#>  [2,]    2    1    2
#>  [3,]    0    2    3
#>  [4,]    1    3    1
#>  [5,]    1    3    1
#>  [6,]    0    2    3
#>  [7,]    2    3    0
#>  [8,]    0    5    0
#>  [9,]    1    1    3
#> [10,]    0    2    3

Note that the samples are not uniform over all possible permutations of the possible partitions:

library(data.table)

setorder(as.data.table(rpart(1e6, 5, 3))[,.(count = .N), V1:V3])[]
#>     V1 V2 V3 count
#>  1:  0  0  5 27939
#>  2:  0  1  4 55609
#>  3:  0  2  3 55284
#>  4:  0  3  2 55460
#>  5:  0  4  1 55240
#>  6:  0  5  0 55658
#>  7:  1  0  4 27985
#>  8:  1  1  3 55582
#>  9:  1  2  2 55990
#> 10:  1  3  1 55421
#> 11:  1  4  0 55702
#> 12:  2  0  3 28025
#> 13:  2  1  2 55605
#> 14:  2  2  1 55430
#> 15:  2  3  0 55384
#> 16:  3  0  2 27757
#> 17:  3  1  1 55304
#> 18:  3  2  0 55702
#> 19:  4  0  1 27584
#> 20:  4  1  0 55338
#> 21:  5  0  0 28001
#>     V1 V2 V3 count

ThomasIsCoding · Answer 3 · 2023-08-23T14:19:48.187

If you are after just one sample instance, you can try

f <- function(i, n) {
    if (n == 1) {
        return(i)
    }
    p <- sample(0:i, 1)
    c(p, Recall(i - p, n - 1))
}

and you can try, for example

> replicate(10, f(5, 3))
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    4    0    2    4    0    4    1    0    5     2
[2,]    0    5    1    1    5    0    1    1    0     1
[3,]    1    0    2    0    0    1    3    4    0     2

If you want all permuations, you can simply define a recursion function f1 or f2 like below

f1 <- function(i, n) {
    if (n == 1) {
        return(i)
    }
    r <- lapply(0:i, \(k) {
        Map(c, k, f1(i - k, n - 1))
    })
    unlist(r, recursive = FALSE)
}

or

f2 <- function(i, n) {
    if (n == 1) {
        return(i)
    }
    r <- lapply(0:i, \(k) {
        cbind(k, f2(i - k, n - 1))
    })
    unname(do.call(rbind, r))
}

and you will see

> f1(5, 3)
[[1]]
[1] 0 0 5

[[2]]
[1] 0 1 4

[[3]]
[1] 0 2 3

[[4]]
[1] 0 3 2

[[5]]
[1] 0 4 1

[[6]]
[1] 0 5 0

[[7]]
[1] 1 0 4

[[8]]
[1] 1 1 3

[[9]]
[1] 1 2 2

[[10]]
[1] 1 3 1

[[11]]
[1] 1 4 0

[[12]]
[1] 2 0 3

[[13]]
[1] 2 1 2

[[14]]
[1] 2 2 1

[[15]]
[1] 2 3 0

[[16]]
[1] 3 0 2

[[17]]
[1] 3 1 1

[[18]]
[1] 3 2 0

[[19]]
[1] 4 0 1

[[20]]
[1] 4 1 0

[[21]]
[1] 5 0 0


> f2(5, 3)
      [,1] [,2] [,3]
 [1,]    0    0    5
 [2,]    0    1    4
 [3,]    0    2    3
 [4,]    0    3    2
 [5,]    0    4    1
 [6,]    0    5    0
 [7,]    1    0    4
 [8,]    1    1    3
 [9,]    1    2    2
[10,]    1    3    1
[11,]    1    4    0
[12,]    2    0    3
[13,]    2    1    2
[14,]    2    2    1
[15,]    2    3    0
[16,]    3    0    2
[17,]    3    1    1
[18,]    3    2    0
[19,]    4    0    1
[20,]    4    1    0
[21,]    5    0    0

Randomly partition an integer into n parts, with zero a possible outcome

3 Answers3

Original Answer

Linked