Multiset partitions
Enchufa2 opened this issue · 2 comments
I reached this repo while looking for R packages for computing multiset partitions, but I may be misunderstanding the documentation. I tried with partitionsGeneral
, but I don't understand the output.
To set a common ground, let me use an example. Let's take the multiset
$\{1,1,2,3\}$ $\{1\},\{1,2,3\}$ $\{2\},\{1,1,3\}$ $\{3\},\{1,1,2\}$ $\{1,1\},\{2,3\}$ $\{1,2\},\{1,3\}$ $\{1\},\{1\},\{2,3\}$ $\{1\},\{2\},\{1,3\}$ $\{1\},\{3\},\{1,2\}$ $\{2\},\{3\},\{1,1\}$ $\{1\},\{1\},\{2\},\{3\}$
Is it possible to get this with this package?
Hello @Enchufa2,
Currently, the partition functions in RcppAlgos
are for integer partitions. For example, if you want to find all of the partitions of 5 of length 3, we would do something like:
partitionsGeneral(5, 3, repetition = TRUE)
#> [,1] [,2] [,3]
#> [1,] 1 1 3
#> [2,] 1 2 2
What you are asking for is known as set partitions.
The excellent partitions
package has some functionality around this topic. Check out this vignette: Set Partitions in R
Hope this helps!
Joseph
Thanks for the pointer, but the partitions
package supports set partitions, as you said, which is not the same problem as multiset partitions. Citing Knuth in The Art of Computer Programming (section 7.2.1.5),
Partitions of a multiset. The partitions of an integer and the partitions of a set are just the extreme cases of a far more general problem, the partitions of a multiset. Indeed, the partitions of
$n$ are essentially the same as the partitions of$\{1 , 1 , ...,1 \}$ , where there are$n$ 1s.
I was hoping that this is what I was looking for, but it's not clear to me where this is called from the R interface.