Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

r

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:

[1] 4 0 1

[2] 2 2 1

[3] 0 2 3

[4] 1 1 3 

Thanks!

like image 336
VeBeKay Avatar asked Sep 03 '25 03:09

VeBeKay


2 Answers

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.

like image 90
Pierre L Avatar answered Sep 06 '25 11:09

Pierre L


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
like image 23
jblood94 Avatar answered Sep 06 '25 11:09

jblood94