Fannkuch是如何工作的？

Question

我对实现Fannkuch的指令感到困惑。 指令：http://www.haskell.org/haskellwiki/Shootout/Fannkuch 在“计算翻转次数，这里是5”之后，我不知所措。

- mudgen

Answer 1

哇，是的，这不是最好的算法描述 :)

我的理解是他们希望你执行以下操作：

fannkuch(n) {
 int maxFlips = 0, printCount = 0;
 遍历[1..n]的排列p {
  maxFlips = max(maxFlips, flipCount(p));
  如果(printCount++ < 30) 打印排列(p);
 }
 打印(maxFlips);
}
flipCount(p) {
 int count = 0;
 当(p[0] != 1)时 {
  反转(p, p + p[0]);
  count++;
 }
 返回count;
}

- Gary Linscott

---

谢谢Gary。我现在理解了，但是我注意到似乎有一种正确的排列顺序被打印出来。我现在正在尝试理解为什么会打印那30个特定的排列，以及为什么是按照那个顺序。 - mudgen

具体的排列顺序并不重要。该特定顺序是按字典顺序从“最小”到“最大”列出排列的。这通常是像C++中的next_permutation()函数在给定排序列表的情况下的行为方式。有关此内容的有趣文章-> http://marknelson.us/2002/03/01/next-permutation/。 - Gary Linscott

那么这个包含30个排列的列表只是生成第一个排列的函数的结果吗？它们并不完全按字典顺序排列。第四个和第五个排列不是按字典顺序排列的。 - mudgen

哎呀，你说得完全正确。我只读了前几个排列。看起来他们有一个明确定义的排列顺序，这在网站上的PS文件中以C或Lisp的形式给出。一些给定的Haskell示例甚至有“这不使用正确的排列顺序”：)。 - Gary Linscott

Answer 2

请查看基准测试游戏 - Fannkuch

要求打印前30个排列只是限制可以对算法进行的可接受更改的简单方法。

- igouy