代码之家 › 专栏 › 技术社区 › j_d

这个组合生成递归有什么问题?

powerset permutation combinations algorithm javascript

0

j_d · 技术社区 · 7 年前

我有以下代码:

const findMult_3 = (num) => {
  const powerset = (set) => {
    const combinations = []
    const combine = (prefix, chars) => {
      for (let i = 0; i < chars.length; i++) {
        combinations.push(prefix + chars[i])
        combine(prefix + chars[i], chars.slice(i + 1))
      }
    }
    combine('', set)
    return combinations
  }

  const allCombinations = powerset(num.toString().split(''))
  console.log(allCombinations)

}
findMult_3(362)

不过,我希望这项工作在 362

[ '3', '36', '362', '32', '6', '62', '2' ]

63, 23, 26 等等,看起来 slice

2 回复 | 直到 7 年前

1

j_d 7 年前

仍然不能百分之百确定问题出在哪里 slice 调用,但我回避了这个问题,并避免了对数组的修改:

const findMult_3 = (num) => {

  const powerset = (set) => {
    const combinations = []
    const combine = (prefix, chars) => {
      for (let i = 0; i < chars.length; i++) {
        combinations.push(prefix + chars[i])
        combine(prefix + chars[i], chars.filter((x, ind) => ind !== i))
      }
    }
    combine('', set)
    return combinations
  }
  
  const allCombinations = powerset(num.toString().split(''))

  console.log(allCombinations)

}

findMult_3(362)

注意使用 filter splice ,保持不变性。

2

-1

José Matos 7 年前

我发现了问题,复制数组(到c),然后删除要与之组合的元素:

const findMult_3 = (num) => {
  const powerset = (set) => {
    const combinations = []
    const combine = (prefix, chars) => {
      console.log(chars);
      for (let i = 0; i < chars.length; i++) {
        combinations.push(prefix + chars[i])
        var c = chars.slice();
        c.splice(i,1);
        combine(prefix + chars[i],  c);
      }
    }
    combine('', set)
    return combinations
  }

  const allCombinations = powerset(num.toString().split(''));
  console.log(allCombinations);