Suppose we have some list of natural numbers $\{ 1, 2, \dots, N \}$ and each natural number $i$ has a 'weight' $w_i$. I would like to generate the all the integer partitions which satisfy the following conditions:
- The partition sums to less than or equal to $M$,
- The partition has length less than or equal to $K$,
- The partition has weight which sums to less than or equal to $W$.
- The entries of the partition are in descending order.
- The allowed entries of partitions are those in our list of natural numbers $\{ 1, 2, \dots, N \}$.
For instance suppose our list of natural numbers is $\{ 1, 2, 3 \}$ with weights $\{ 2, 3, 5 \}$ and we have $M=4,K=2, W=8$. In this case $\left( 1, 3 \right)$ is a partition with total weight $2+5=7$ so would be included. However $\left( 1, 1, 1 \right)$ has more than $K=2$ entries so is invalid. Similarly $\left( 3, 3 \right)$ has total weight $5+5=10$ which is over our limit $W=8$ and has sum $3+3=6$ which is also over our limit of $M=4$. Finally $\left( 4 \right)$ is an invalid partition because it involves a number outside our list $\{ 1, 2, 3 \}$.
Using the given example, I tried:
list = {1, 2, 3};
weights = {2, 3, 5};
M = 2;
K = 4;
W = 8;
checkWeight[partition_, weight_] :=
Sum[weight[[partition[[i]]]], {i, 1, Length[partition]}] <= W;
allPartitions =
Flatten[Table[IntegerPartitions[i, K, list], {i, 1, M}], 1]
myPartitions =
Table[If[checkWeight[allPartitions[[i]], weights],
allPartitions[[i]], Nothing], {i, 1, M}]
The trouble is the numbers I am working with in practice look more like
list = Table[i, {i, 1, 25}];
weights = Table[Mod[i, 5] + 1, {i, 1, 25}];
M = Length[list]*K;
K = 5;
W = 5;
In this case allPartitions contains approximately $140,000$ elements while myPartitions contains $23$ elements. Consequently I'd like to find an alternative solution that doesn't waste resources computing so many unnecessary elements only to throw almost all of them away.
