Partitioning into multiple subsets

[fcocquemas]

Hello,

First of all, fantastic library, and incredibly fast. Thank you so much for sharing it.

I'm really terrible at combinatorics, so my problem may have an obvious answer. Is there a straightforward way that I can partition a set into multiple subsets with each its own number of elements and constraint sum?

For instance, say that I have a vector v with 11 elements, and I would like to find all partitions in three, such as the subsets have 5, 3, and 3 elements respectively, and sum to 6, 7, and 8 respectively.

v <- c(1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4)
sum(v) # 21 = 6 + 7 + 8
multiComboGeneral(v, m=c(5, 3, 3), limitConstraints=c(6, 7, 8))
# list(list(c(1, 1, 1, 1, 2), c(1, 2, 4), c(2, 3, 3)), ...)

Another output shape would be fine, of course. It's worth noting that I need all elements of v to be selected once and only once.

I can think of a recursive approach using comboGeneral with m=5 and limitConstraints=6, then for each partition repeat on remaining elements with m=3 and limitConstraints=7, then m=3 and limitConstraints=8, and drop the cases that do not work. But, this seems highly inefficient, with a larger vector especially.

Is there a more direct way to do this? Any pointers would be greatly appreciated.

[jwood000]

@fcocquemas,

This is a very interesting problem. I've thought about it from time to time for the past few months and it seems like we will need to implement a more general subset sum algorithm.

I think it can be done and will give it an honest try after the next release.

Thanks