Number of ways to divide n objects in k groups, such that no group will have fewer objects than previously formed groups?

Question

Example: n=8, k=4 Answer: 5

[1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2]

I thought of applying dynamic programming to count the number of ways 8 objects can be divided into 4 groups, but can't understand how to keep track of the number of objects in the previous group.

DP approach:

for(int j=0;j<=n;j++)
{
    for(int i=1;i<=k;i++)
    {
        if(j<i)
            continue;
        if(j==i)
            dp[j]=1;
        for(int k=1;k<i;k++)
        {
            dp[j]+=dp[k]*dp[j-k];
        }
    }
}

Please help with the approach. I'm relatively new to DP.

Solution 1

These are known as partitions with restricted number of parts. The idea behind the recurrence, which is equal to the number of partitions whose largest part is k (proof is left as a short, interesting read) is that if the smallest part of the partition is 1, we've added 1 to all partitions of n - 1 into k - 1 parts (to guarantee the smallest part is 1); and if the smallest part is not 1, we've added 1 to each of k parts in all partitions of n - k into k parts (guaranteeing that each part is greater than 1).

Here's a straightforward memoization:

function f(n, k, memo={}){
  if (k == 0 && n == 0)
    return 1

  if (n <= 0 || k <= 0)
    return 0

  let key = String([n, k]) // Thanks to comment by user633183

  if (memo.hasOwnProperty(key))
    return memo[key]

  return memo[key] = f(n - k, k, memo) + f(n - 1, k - 1, memo)
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')

Here's bottom-up:

function f(n, k){
  let dp = new Array(n + 1)
  for (let i=0; i<n+1; i++)
    dp[i] = new Array(k + 1).fill(0)
  dp[0][0] = 1
  
  for (let i=1; i<=n; i++)
    for (let j=1; j<=Math.min(i, k); j++)
      dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1]

  return dp[n][k]
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')

Solution 2

Update

Although all the discussion below is still useful, the answer from גלעד ברקן provides a much nicer underlying algorithm that allows us to skip my min parameter. (I knew I should have looked this up!) That understanding allows for significant performance improvement over the algorithm used below.

---

Think of dynamic programming (DP) as a simple optimization technique that can speed up certain recursive procedures. If your recursive calls are repeated (as with the Fibonacci numnbers), then storing their results can drastically speed up your program. But the underlying logic is still a recursive call. So let's solve this program recursively first and see where we might apply DP optimization.

(8, 4) with only five solutions is small enough that, even if the time is algorithmically exponential, it's still probably manageable. Let's try a simple recursion. And at first, let's actually build the output rather than count it in order to double-check that we're doing things right.

This version is based on the idea that we can set the first number of the list, keeping track of that value as a minimum for the remaining elements, and then recurring for the remaining positions. Finally, we try again with a higher initial number. So as well as our n and k inputs, we will also need to keep a min parameter, which we start at 1.

Here is one version:

const f = (n, k, min = 1) => 
  k < 1 || n < k * min
    ? []
  : k == 1
    ? [[n]]
  : [
      ... f (n - min, k - 1, min) .map (xs => [min, ...xs]), 
      ... f (n, k, min + 1)
    ]

console .log (
  f (8, 4) //~> [[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]]
)

(You didn't specify a language tag; if that Javascript ES6 syntax is not clear, we can rewrite in another style.)

Since that seems right, we can write a simpler version just to count the results:

const f = (n, k, min = 1) => 
  k < 1 || n < k * min
    ? 0
  : k == 1
    ? 1
  : f (n - min, k - 1, min) + f (n, k, min + 1)

console .log (
  f (8, 4) //~> 5
)

But if we are going to try a larger set, say f(1000, 10) (which, by inspection, should be 886745696653253¹), it might take a bit of time to calculate. Our algorithm is likely exponential. So there are two ways we might go about dynamic programming for this. The most obvious is the bottom-up approach:

const f = (_n, _k, _min = 1) => {
  const cache = {}
  for (let n = 1; n <= _n; n ++) {
    for (let k = 1; k <= Math.min(_k, n); k++) {
      for (let min = n; min >= 0; min--) {
        cache [n] = cache[n] || {}
        cache [n] [k] = cache [n] [k] || {}
        cache [n] [k] [min] = 
          k < 1 || n < k * min
            ? 0
            : k == 1
               ? 1
               : cache [n - min] [k - 1] [min]  + cache [n] [k] [min + 1]
      }
    }
  }
  return cache [_n] [_k] [_min]
}

console.time('time taken')
console .log (
  f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')

Figuring out the correct bounds here is tricky, if for no other reason, because the recursion is based on an increasing value of min. It's likely that we're calculating things we don't need along the way.

It's also ugly code, losing the elegance and readability of the original while gaining only performance.

We can still keep the elegance by memoizing our function; this is the top-down approach. By working with a reusable memoize function, we can use our recursive solution almost intact:

const memoize = (makeKey, fn) => {
  const cache = {}
  return (...args) => {
    const key = makeKey(...args)
    return cache[key] || (cache[key] = fn(...args))
  }
}

const makeKey = (n, k, min) => `${n}-${k}-${min}`        
        
const f = memoize(makeKey, (n, k, min = 1) => 
  k < 1 || n < k * min
    ? 0
  : k == 1
    ? 1
  : f (n - min, k - 1, min)  + f (n, k, min + 1)
)

console.time('time taken')
console .log (
  f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')

memoize turns a function that calculates its results on every call into one that only calculates them the first time it sees a certain set of input. This version requires you to supply an additional function that turns the arguments into a unique key. There are other ways this could be written, but they are a bit uglier. Here we just turn (8, 4, 1) into "8-4-1", then store the result under that key. There's no ambiguity. The next time we call with (8, 4, 1), the already-calculated result will be returned instantly from the cache.

Note that there is a temptation to try

const f = (...args) => {...}
const g = memoize(createKey, f)

But this doesn't work, if the recursive calls in f point back to f. And if they point to g, we've already mixed up the implementation and f is no longer stand-alone, so there's little reason for it. Thus we write it as memomize(createKey, (...args) => {...}). Advanced techniques that offer alternatives are beyond the scope of discussion here.

---

Deciding between bottom-up DP and top-down DP is a complicated question. You will see in the case above that the bottom-up version runs faster for the given input. There is some recursive overhead to the additional function calls, and you might in some cases be subject to recursion depth limits. But this is sometimes entirely offset by the top-down technique only calculating what you need. Bottom-up will calculate all smaller inputs (for some definition of "smaller") in order to find your value. Top-down will only calculate those values necessary for solving your problem.

---

¹ A joke! I only found the value after using dynamic programming.