The setup
I have two unordered partitions of N - example: 25 = 1 + 1 + 4 + 5 + 14 and 25 = 2 + 11 + 12. On each partitions I can only apply a refinement, which is to further partition one of its partitions (except for 1), and the goal is to make both partitions equal. So one way to do this would make both partitions 25 = 1 + 1 + 2 + 4 + 5 + 12, where in the first partition 14 = 2 + 12 and on the second 2 = 1 + 1 and 11 = 2 + 4 + 5.
The problem
Is there a way to guarantee that we always use the minimal amount of refinements, where we measure the cost by the number of additional "+" or sub-partitions? So in the above example, the cost is 4 because we partitions 14 once, 2 once, and 11 twice. But we could have also refined more aggressively so that 25 = 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 + 4 + 5, but is not minimal. Alternatively: Can we calculate the minimal cost with some fast procedure (without knowing the actual partition)?
A proposed approach - brute force (could be faster?)
For partition $N_i = \sum_j a_{ij}$.
- Generate partitions for $a_{ij}=\sum_k b_{ijk}\rightarrow P_{ijm}$.
- Combine $P_{im} := \wedge_j P_{ijm}$ and sort $P_{im}$.
- Compare $P_{0m}$ and $P_{1m}$, and only keep equivalent pairs, $P_{m}$
- Sort by $|P_{m}|$ and use the smallest.
I think that we can potentially improve performance if we isolated step 1 to begin with partitions of size 1 and 2, apply the rest of the steps, calculating some measure of how close we might be to an answer along the way to help prioritise which partitions to check next. Having some idea as to the minimal cost ahead of time (without knowing how) can help in this regard.