Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top