In the game idle heroes, demon bells can be level 1,2,3,4. A level 4 is made of 4 level 1, a level 3 is made of 3 level 1 and so on.

I want to find all arrangements of db given a fixed number. I made this recursive algorithm in javascript:

Closer with a more simplified approach:

function findDB(numDB, arr) {
  console.log("findDB" numDB);
  if (numDB == 1) {
    console.log("HERE2");
    return 1;
  } else {
    for (let i = 1; i < numDB; i  ) {
      console.log("FOR" i);
      console.log("COND"  (numDB   (numDB-i)));
      if((numDB   (numDB-i)) > numDB 1)
        continue;
      arr= arr.concat([numDB,[i,findDB(numDB - i, arr)]]);
    }
    return arr;
  }
}
var final = []
var y = findDB(3, final);
console.log(JSON.stringify(y));

Output:

findDB(2) CORRECT!

findDB2
FOR1
COND3
findDB1
HERE2
[2,[1,1]]

FindDB(3) is missing 1,1,1,

findDB3
FOR1
COND5
FOR2
COND4
findDB1
HERE2
[3,[2,1]]

here is intended output for input 1 through 6 (algo needs to scale for any number input)

    /1/ (1)
    /2/ (2),
        (1,1)
    /3/ (3),
        (2,1),
        (1,1,1)
    /4/ (4),
        (3,1),
        (2,2),(2,1,1),
        (1,1,1,1)
    /5/ (4,1),
        (3,2),(3,1,1),
        (2,2,1),(2,1,1,1),
        (1,1,1,1,1)
    /6/ (4,2),(4,1,1),
        (3,3),(3,2,1),(3,1,1,1),
        (2,2,2),(2,2,1,1),(2,1,1,1,1)
        (1,1,1,1,1,1)

CodePudding user response：

Here is a recursive function that produces the results you want. It attempts to break down the input (numDB) into parts up to the maximum number (maxDB, which defaults to 4). It does this by taking the numbers from numDB down to 1 and adding all the possible results from a recursive call to that number, noting that the value of maxDB has to change to be no more than the first number.

const findDB = function(numDB, maxDB = 4) {
  if (numDB == 0) return [ [] ];
  let result = [];
  let thisDB = Math.min(numDB, maxDB);
  for (let i = thisDB; i > 0; i--) {
    findDB(numDB - i, Math.min(i, thisDB)).forEach(n => {
      result.push([i].concat(n));
    });
  }
  return result;
}

console.log(findDB(5))

.as-console-wrapper {
  min-height: 100% !important;
}

CodePudding user response：

This is called the partitions of a number, and is a well-known problem. I'm sure computer scientists have more efficient algorithms than this, but a naive recursive version might look like this:

const partitions = (n, m = n) =>
  m > n
    ? partitions (n, n)
  : m == 1
    ? [Array (n) .fill (1)]
  : m < 1
    ? [[]]
  : [
      ... partitions (n - m, m) .map (p => [m, ...p]),
      ... partitions (n, m - 1)
    ];

[1, 2, 3, 4, 5, 6] .forEach ((n) => console .log (`${n}: ${JSON .stringify (partitions (n))}`))

And if you're worried about the default parameter (there sometimes are good reasons to worry), then you can just make this a helper function and wrap it in a public function like this:

const _partitions = (n, m) =>
  m > n
    ? _partitions (n, n)
  : m == 1
    ? [Array (n) .fill (1)]
  : m < 1
    ? [[]]
  : [
      ... _partitions (n - m, m) .map (p => [m, ...p]),
      ... _partitions (n, m - 1)
    ];

const partitions = (n) => _partitions (n, n);

[1, 2, 3, 4, 5, 6] .forEach ((n) => console .log (`${n}: ${JSON .stringify (partitions (n))}`))

in either case, n is the integer we're summing to, and m is the maximum integer we can use. If m is too large, we simply call again with an appropriate m. If it equals 1, then we can only have an array of n 1's. If m reaches zero, then we have only the empty partition. Finally, we have two recursive cases to combine: When we choose to use that maximum number, we recur with the remainder and that maximum, prepending the maximum to each result. And when we don't use the maximum, we recur with the same target value and a decremented maximum.

I feel as though this has too many cases, but I don't see immediately how to combine them.

The time is exponential, and will be in any case, because the result is exponential in the size of n. If we added memoization, we could really speed this up, but I leave that as an exercise.

Update

I was bothered by those extra cases, and found an Erlang answer that showed a simpler version. Converted to JS, it might look like this:

const countdown = (n) => n > 0 ? [n , ...countdown (n - 1)] : []

const _partitions = (n, m) =>
  n < 0
    ? []
  : n == 0
    ? [[]]
  : countdown (m) .flatMap (x => _partitions (n - x, x) .map (p => [x, ...p])) 

We have a quick helper, countdown to turn, say 5 into [5, 4, 3, 2, 1]. The main function has two base cases, an empty result if n is negative and a result containing only the empty partition if n is zero. Otherwise, we countdown the possibilities for the maximum value in a single partition, and recur on the partitions for the target less than this new maximum, adding the maximum value to the front of each.

This should have similar performance characteristics as the above, but it somewhat simpler.