2
$\begingroup$

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:

  1. The partition sums to less than or equal to $M$,
  2. The partition has length less than or equal to $K$,
  3. The partition has weight which sums to less than or equal to $W$.
  4. The entries of the partition are in descending order.
  5. 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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

It looks like Solve can deal with this problem directly.

list = Range[25];
weights = Mod[list, 5] + 1;
k = 5;
m = Length[list] * k;
w = 5;

Define a vector $\vec{v}$ whose coefficients $c_i$ count how many times the element $i$ appears in the solution:

v = Array[c, Length[list]];

Solve for the vector $v$ to find all 786 solutions:

s = SolveValues[1 <= Total[v] <= k &&
                list . v <= m &&
                weights . v <= w,
                v, NonNegativeIntegers]

(*    {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
       ...
       {2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
       {2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}    *)

To convert these solutions into the form you want:

Reverse[Join @@ MapThread[ConstantArray, {list, #}]] & /@ s

(*    {{25}, {25, 25}, {25, 25, 25}, {25, 25, 25, 25}, {25, 25, 25, 25, 25},
       {24}, {23}, {25, 23}, {22}, {25, 22}, {25, 25, 22}, {21},
       ...
       {5, 5, 5, 1}, {2, 1}, {1, 1}, {25, 1, 1}, {20, 1, 1}, {15, 1, 1}, {10, 1, 1}, {5, 1, 1}}    *)
$\endgroup$
1
  • $\begingroup$ Exactly what I was looking for, thanks! $\endgroup$ Dec 18, 2023 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.