0
$\begingroup$

Say I have some multiset of integers, for example $M1=\{6,6,4,4,4,2,2\}$.

I have a second multiset that consists of some set of valid sums derived from picking without replacement from $M1$, say for example $M2=\{16,8,4\}$

I'd like to count the number of ways that $M2$ can be formed from $M1$. In the simple example above, the valid picks are

$ \begin{array}{ccc} \{2,2,6,6\} & \{4,4\} & \{4\} \\ \{2,4,4,6\} & \{2,6\} & \{4\} \\ \{4,6,6\} & \{2,2,4\} & \{4\} \\ \{4,6,6\} & \{4,4\} & \{2,2\} \\ \end{array} $

So the desired result is $4$.

I'm currently doing this algorithmically by getting the integer partitions of each element in $M2$ restricted to members of $M1$, then eliminating invalid ones, then doing a cartesian product of those sets, and eliminating those that are invalid (e.g., tally of elements does not match that of $M1$).

Obviously, this gets inefficient quickly.

Is there some combinatorial structure that enumerates this kind of thing? I poked through my copy of Andrews' and searched via Google scholar and came up blank.

$\endgroup$
0
$\begingroup$

I suspect you could do this recursively.

So starting with $M1$, there are only two ways of getting elements to add up to $4$: $\{2,2\}$ and $\{4\}$.

From $M1\text{\\} \{2,2\}=\{6,6,4,4,4\}$ there is one way of getting elements to add up to $8$: $\{4,4\}$. From $M1\text{\\} \{2,2,4,4\}=\{6,6,4\}$ there is one way of getting elements to add up to $16$.

From $M1\text{\\} \{4\}=\{6,6,4,4,2,2\}$ there are three ways of getting elements to add up to $8$: $\{2,2,4\}$, $\{2,6\}$, $\{4,4\}$. From each of what remains there is one way of getting elements to add up to $16$.

Hence your four examples.

Just repeat doing this. You already have to deduplicate when $M1$ has repeated elements, and you may need to do so when $M2$ does. My guess is that it may be easier to take the smaller elements of $M2$ as early targets, though no doubt there are particular examples where the reverse is true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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