2

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)
Improve this question
11
  • 1
    Your algorithm is pretty much hardcoded. Try to make it more abstract - have a single base case, and a single recursive case (use a loop!). Ensure that you always return an array of arrays of numbers. Commented Apr 27, 2022 at 3:29
  • Is an input of more than 5 valid? If so, what would be the expected output for an input of (say) 6? Commented Apr 27, 2022 at 3:43
  • @Nick yes I want this to scale for any number (realistically only going to 30). Expected output for 6 is added to question Commented Apr 27, 2022 at 3:50
  • Is (4) a valid response for an input of 4? Commented Apr 27, 2022 at 4:02
  • yes @Nick I added 1 through 6 to question Commented Apr 27, 2022 at 4:09

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Amazing. performance not a concern for me as only using up to n=30. Thank you!!
1

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;
}
;
[6, 5, 4, 3, 2, 1].forEach((i) => console.log(JSON.stringify(findDB(i))))
.as-console-wrapper {
  min-height: 100% !important;
}

I've written the above function in the style in your question, with the use of various ES6 Array methods it can be simplified:

const DBlist = (n) => [...Array(n).keys()].map(k => n - k)

const findDB = (numDB, maxDB = 4) => {
  if (numDB == 0) return [ [] ];
  const thisDB = Math.min(numDB, maxDB);
  return DBlist(thisDB).flatMap((i) => findDB(numDB - i, Math.min(i, thisDB)).map(a => [i, ...a]))
}

DBlist(6).forEach((n) => console.log(JSON.stringify(findDB(n))))
.as-console-wrapper {
  min-height: 100% !important;
}

Improve this answer

1 Comment

@WinWinWinWin I've added an ES6 version of my code if it's of interest

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.