2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

You want to enumerate all integer partitions of $v$ into exactly $\ell$ parts, where each part is $\le b$. Let $F(v,\ell,b)$ denote the set of all such partitions.

One can construct a recursive algorithm for this. For instance, any such partition must include the number $b$ one, two, three, ..., or $\lfloor v/b \rfloor$ times, so:

$$F(v,\ell,b) = \bigcup_{i=0}^{\lfloor v/b \rfloor} F(v-ib,\ell-1,b-1) + b+\cdots + b,$$

where $F(\star)+b+\cdots+b$ represents the set of partitions (multisets) obtained by starting with each partition in $F(\star)$ and adding $i$ copies of the number $b$ to it. Moreover, this is a disjoint union, so there is no need to use hashtables to eliminate duplicates.

However, the number of such partitions can be exponentially large in $v$, so in general the algorithm might be infeasibly expensive, unless $v$, $\ell$, or $b$ are sufficiently small.

$\endgroup$
3
  • $\begingroup$ Thanks so much, your answer perfectly solves my question and gives the formal definition of it. After reading your answer I didn't comment immediately because I was busying doing other things and also trying to understand as much as possible about integer partitions before I ask you another question, however the concept about integer partition does help me enough to solve my extended question in this page, can you please answer that also or should I open another question and invite you to answer? $\endgroup$
    – Li Wang
    May 11, 2017 at 13:03
  • $\begingroup$ @user3171410, glad it helped! I suggest asking a separate question - this site works best when there is only one question per post. $\endgroup$
    – D.W.
    May 11, 2017 at 14:13
  • $\begingroup$ Sorry to bring this up again, but can you please also give the exact time complexity in terms of $v$,$\ell$ and $b$? $\endgroup$
    – Li Wang
    Jul 25, 2017 at 14:36

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.