时间戳

首页 > 解决方案 > JavaScript 将原始数组保留在递归函数中

javascript - JavaScript 将原始数组保留在递归函数中

问题描述

我想保留原始数组以在递归函数中返回原始索引。原始代码来自 rbarilani https://gist.github.com/rbarilani/0d7946510740f9e1e8fa。请帮忙告知如何更改线路

const numList = [3,9,8,4,5.5,7,10.07];

function subsetSum(numbers, target, partial) {
  var s, n, remaining;
  const numList = [3,9,8,4,5.5,7,10.07]; **//<<<<<<<The code I want to change, please advise how to make it as function input**     
  partial = partial || [];

  // sum partial
  s = partial.reduce(function (a, b) {
    return Math.round((a + b)*100)/100;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target) {
    console.log(numList);
    partial.forEach(function(findIndex){
    console.log(findIndex, 'is at position ', numList.indexOf(findIndex));
});
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([3,9,8,4,5.5,7,10.07],15.57);

谢谢你们

标签： javascriptarraysrecursion

解决方案

我会推荐生成器，因为它们非常适合此类问题。生成器的好处是它是可暂停和可取消的。这使您可以轻松找到问题的一种解决方案或所有解决方案，而无需更改代码。

function* subsetSums(numbers, target, precision = 2)
{ function* solve(i, q, r)
  { if (q == 0) return yield r
    if (numbers.length < i || q < 0) return
    // solve with this number
    yield *solve
      ( i + 1
      , round(q - numbers[i], precision)
      , [...r, {pos: i, n: numbers[i]}]
      )
    // solve without this number
    yield *solve(i + 1, q, r)
  }
  yield *solve(0, target, [])
}

注意我是如何分离round成它自己的功能的。隔离关注点是一种有效的编程技术，因为它使您的函数更易于读/写，并促进了程序其他区域内的代码重用

const round = (n, p = 0) =>
  Math.round(n * 10 ** p) / 10 ** p

我们可以得到所有的解决方案——

const solutions =
  Array.from(subsetSums([3.27,9,8,6.8,4,5.5,7,10.07], 15.57))

或者，也许我们只是想要first解决方案。因为生成器是可取消的，这意味着在返回第一个值后不会做任何工作——

function first (it)
{ for (const v of it)
    return v
}

const solution =
  first(subsetSums([3.27,9,8,6.8,4,5.5,7,10.07], 15.57))

form我们可以使用一些额外的通用函数将其包装到一个简单的 HTML中stepper，它会逐步执行任何生成器，并且json它会创建一个带有JSON.stingify'd 内容的文本节点 -

function* stepper (it, f)
{ let x = it.next()
  while (!x.done) (yield f(x.value), x = it.next())
  while (true) yield f("no more results")
}

function json(value)
{ const e = document.createElement("pre")
  e.textContent = JSON.stringify(value)
  return e
}

现在我们要做的就是将它连接到我们的表单 -

<form id="solver">
  <button type="button" name="next">next</button>
  <output name="output"></output>
</form>

const f =
  document.forms.solver
  
const solver =
  stepper
    ( subsetSums([3.27,9,8,6.8,4,5.5,7,10.07], 15.57)
    , solution => 
        f.output.appendChild(json(solution))
    )
    
f.next.addEventListener("click", _ => solver.next())

运行下面的代码片段以在您自己的浏览器中查看结果 -

function* subsetSums(numbers, target, precision = 2)
{ function* solve(i, q, r)
  { if (q == 0) return yield r
    if (numbers.length < i || q < 0) return
    // solve with this number
    yield *solve
      ( i + 1
      , round(q - numbers[i], precision)
      , [...r, {pos: i, n: numbers[i]}]
      )
    // solve without this number
    yield *solve(i + 1, q, r)
  }
  yield *solve(0, target, [])
}

function* stepper (it, f)
{ let x = it.next()
  while (!x.done) (yield f(x.value), x = it.next())
  while (true) yield f("no more results")
}

function json(value)
{ const e = document.createElement("pre")
  e.textContent = JSON.stringify(value)
  return e
}

const round = (n, p = 0) =>
  Math.round(n * 10 ** p) / 10 ** p

const f =
  document.forms.solver
  
const solver =
  stepper
    ( subsetSums([3.27,9,8,6.8,4,5.5,7,10.07], 15.57)
    , solution => 
        f.output.appendChild(json(solution))
    )
    
f.next.addEventListener("click", _ => solver.next())
<form id="solver">
  <button type="button" name="next">next</button>
  <output name="output"></output>
</form>

[{"pos":0,"n":3.27},{"pos":3,"n":6.8},{"pos":5,"n":5.5}]
[{"pos":5,"n":5.5},{"pos":7,"n":10.07}]
"no more results"

numbers输入不会因为运行而被修改subsetSums。

推荐阅读