I'm trying to solve the following problem.
Input
- positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.)
Output
A list $S_1, \dots, S_k$ of all possible integer multisets (a generalization of the concept of a set that, unlike a set, allows multiple instances of the multiset's elements), such that each $S_i$ fulfills following constraints:
- $|S_i|=\ell$
- $\sum_{s\in S_i}s=v$
- for all $s\in S_i$, $s\in \{1, \dots, b\}$
For example, a solution to the instance $v=4$, $b=4$, $\ell=2$, is $[\{1,3\},\{2,2\}]$.
For now I have a recursive function working to give something not exactly the same as what I'm expecting. For the input above, it returns $[\{1,3\},\{2,2\},\{3,1\}]$. I know I can use extra steps to eliminate the duplicates but I'm wondering if there's a mathematical formula I can use? Or some other algorithm acts smarter?
Below is my code:
public static List<List<Integer>> getIntegerSets(int v, int base, int l) {
if (v < l || l <= 0) return null;
List<List<Integer>> result = new ArrayList<>();
if (l == 1) {
if (v > base) return null;
List set = new ArrayList<Integer>();
set.add(v);
result.add(set);
} else {
for (int i = Math.min(base, l * v); i > 0; i--) {
List<List<Integer>> list = getIntegerSets(v - i, base, l - 1);
if (list == null) continue;
for (List<Integer> subset : list) {
subset.add(0, i);
result.add(subset);
}
}
}
return result;
}
Another extended problem is, can we (use another algorithm) directly get the size of the list, which is the $k$ value, with or without duplicates, perfectly both, without executing this very function?