计算'permutations xs`的'长度'

在Haskell的GHCi中，输入length$ permutations [1..8]，这是即时的。用length$ permutations [1..16]你看... ..分钟，小时也许？如果我们想要的是permutations xs会产生（即不需要贯穿它们）的结果的实际数量，那么显然必须有一个简单的便宜公式，只知道xs的length。计算'permutations xs`的'长度'

我与数学令人遗憾的是缓慢的，但鉴于len = length xs，我注意到，答案是通过给予任何积极len，从中发现：

numofperms 0 = 0 
numofperms 1 = 1 
numofperms ln = ln * (numofperms (ln - 1))

不过，虽然这明显低于评估所有的permutations，为什么快递归！我确信有一个'公式'隐藏在那里，我不能立即/直觉地看到。如何将上述逻辑转化为简单的非递归数学计算？ “有因果关系的东西”还是这样的？

您标记为重复前：我敢肯定，我可以很容易地找到这里容易或elsewere“哪个公式给出排列数回答”，但真正的问题（如果允许这个格式）人们是如何从直观编写的递归逻辑跳转到更便宜和正确的计算，如(x * (x+-foo^bar)) ---这肯定可以成为这方面的教育线程，用于其他未来的功能程序员！

来源

2017-01-13 metaleap

不是“某物*与*阶乘”---只是阶乘本身。另外 - '长度$ permutations [1..16]'可能会导致Haskell崩溃并出现内存错误。 –

“如何从直觉编写的递归逻辑跳转到像'（x *（x + -foo^bar））'' - 数学那样更便宜和更正确的计算，并且它并不总是直观的。对于简单的情况，有一些常见的事情可以尝试，但总的来说，呃......你只需要解决它。 https://en.wikipedia.org/wiki/Closed-form_expression？ – Ryan

@JohnColeman：“长度”不能保留过去的结果，所以Haskell只需要很长时间来评估它。 – Ryan

这一个是不正确：

numofperms 0 = 0

0元素的排列的数量是1（permutations [] == [[]]）。考虑到这一点，也许这将有助于缩短工作时间：

f(0) = 1 
f(n) = n * f(n - 1)

看起来很熟悉吗？这是n！ - factorial。

来源

2017-01-13 14:15:47 Ryan

计算'permutations xs`的'长度'

回答

相关问题