如何在 javascript 中取消嵌套此递归算法？

Question

在游戏idle heroes中，妖铃可以是1,2,3,4级。 4级由4级1组成，3级由3级1组成，依此类推。

我想找到给定固定数字的数据库的所有排列。我在 javascript:

中做了这个递归算法

更简单的方法更接近：

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));

输出：

findDB(2) 正确！

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

FindDB(3) 缺少 1,1,1,

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

这里是输入 1 到 6 的预期输出（算法需要缩放任何数字输入）

    /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)

Answer 1

这是一个递归函数，可以产生你想要的结果。它尝试将输入 (numDB) 分解为最大数量的部分 (maxDB，默认为 4)。它通过将数字从 numDB 下降到 1 并将递归调用的所有可能结果添加到该数字来实现，请注意 maxDB 的值必须更改为 no多于第一个数字。

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;
}

我把上面的函数写成你问题中的样式，使用各种ES6 Array方法可以简化：

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;
}

Answer 2

这称为 partitions of a number，是一个 well-known 问题。我敢肯定计算机科学家有比这更有效的算法，但朴素的递归版本可能如下所示：

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))}`))

而且如果您担心默认参数（有时 good reasons 需要担心），那么您可以将其设为辅助函数并将其包装在 public 函数中，如下所示:

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))}`))

在任何一种情况下，n 是我们求和的整数，m 是我们可以使用的最大整数。如果 m 太大，我们只需使用适当的 m 再次调用。如果它等于 1，那么我们只能有一个 n 1 的数组。如果 m 达到零，那么我们只有空分区。最后，我们有两个递归情况要组合：当我们选择使用那个最大数时，我们用余数和那个最大值递归，将最大值放在每个结果之前。当我们不使用最大值时，我们会以相同的目标值和递减的最大值重复出现。

我觉得这个案例太多了，但我没有立即看到如何将它们组合起来。

时间是指数级的，而且无论如何都会是指数级的，因为结果在 n 的大小上是指数级的。如果我们添加记忆，我们真的可以加快速度，但我把它留作练习。

更新

我被那些额外的案例所困扰，并找到了一个显示更简单版本的 Erlang answer。转换为 JS，它可能是这样的：

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]))

我们有一个快速帮手，countdown 可以将 5 变成 [5, 4, 3, 2, 1]。 main 函数有两个基本情况，如果 n 为负，则结果为空；如果 n 为零，则结果仅包含空分区。否则，我们对单个分区中最大值的可能性进行倒计时，并在小于这个新最大值的目标分区上重复，将最大值添加到每个分区的前面。

这应该具有与上述类似的性能特征，但更简单一些。

如何在 javascript 中取消嵌套此递归算法？

How to un-nest this recursive algorithm in javascript?

javascript

recursion

computer-science

更新