将数学公式转换为node.js

Question

我想使用这里列出的数学公式：

https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets

在node.js中，使用k个字符生成长度为n的唯一环序列的总数可以计算出来，允许重复，并忽略镜像序列。

这个公式需要先计算前面的公式，如下所示：

https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_necklaces

这个“项链数量”公式的结果在“手镯数量”公式中用作Nk(n)。 编辑 这是最终解决方案：

const phi = require('number-theory').eulerPhi
const divisors = require('number-theory').divisors

let n = 6,
  k = 5,
  sum = (arr, func) => arr.reduce( (acc, n) => acc + func(n), 0),
  divisorsArray = divisors(n),
  necklaces = (1/n) * sum(divisorsArray, (d) => phi(d) * k ** (n/d))

let bracelets = (n % 2) ?
  (necklaces/2) + 0.5 * (k ** ((n+1)/2)) :
  (necklaces/2) + 0.25 * (k+1) * (k ** (n/2))

- Matthew

---

你可以使用像这个一样的数学库：https://github.com/arguiot/TheoremJS - Alexandre Nicolas

我也不太理解这个公式^^。我可以向您展示如何在js中创建一个总和（这将是一个很好的开始）：const sum = (nStart, nEnd, myFunction) => { return Array.from(Array(nEnd - nStart)) // 创建一个x元素的空数组 .reduce((acc, item, n) => acc + myFunction(n)) // 检查reduce函数 }sum(0, 100, n => n + 1) - Alexandre Nicolas

这个sigma符号的解释最终描述了你所困惑的用法。请参考：https://zh.wikipedia.org/wiki/%E5%A4%A7%E5%AD%97%E6%A3%80%E6%B1%82. - rici

有关数学符号的问题可能会在[math.se]上获得更好的答案。像你在这里所做的那样，提到您不理解的确切部分总是有帮助的。 - rici

那么，关于项链的第一个公式基本上是：(1 / n) 乘以所有 (ϕ(d) * k * (n / d)) 的总和，其中 d 是所有能够整除 n 的数字？其中 n 是序列长度，k 是可能字符的数量。 - Matthew

Answer 1

这是我的最终解决方案，对我来说可以正常工作。

const phi = require('number-theory').eulerPhi
const divisors = require('number-theory').divisors

let n = 6,
    k = 5,
    sum = (arr, func) => arr.reduce( (acc, n) => acc + func(n), 0),
    divisorsArray = divisors(n),
    necklaces = (1/n) * sum(divisorsArray, (d) => phi(d) * k ** (n/d))

let bracelets = (n % 2) ?
    (necklaces/2) + 0.5 * (k ** ((n+1)/2)) :
    (necklaces/2) + 0.25 * (k+1) * (k ** (n/2))

- Matthew

---

正如在您的问题评论中所指出的那样，如果您正确计算总和，就不需要使用Math.floor :) - rici

看起来不对，如果我从总和中删除 arr[0]，针对 k：5，n：5 我得到的是 64，但如果我把它放回去，我得到的是 377（正确的答案） - Matthew

解决方案不是仅仅删除 arr[0]（这将给你一个不同的错误值）。你需要用 0 替换它。 - rici

啊，对不起，我的错。谢谢你提醒我。我已经更新了代码以反映这一点。 - Matthew

另外，necklaces = divisorsArray.map(d => phi(d) * k ** (n/d)).reduce((a,n) => a+n) / n。在这种情况下，最好在最后进行除法计算，因为该计算是精确的，而1/n除了2的幂次方外都不是精确的。Reduce/map习惯用于像Python这样的语言中，其中map是生成器；在JS中，map会创建一个临时数组。 - rici

我建议您将这些公式重构为const，因为它们不会被更改，也不会在传入的变量之外发生更改。 - Evan Bechtol