haskell - 组合学:圣彼得博弈算法

Question

有一个组合数学难题(如 Jan Gullberg 的数字诞生以来的数学中提到的)，如果您将来自两个类别的 15 个成员(例如 0 类别中的 15 个)排列起来 和 15 个类别 1 总共 30 元素)以特定顺序混合，那么如果您连续沿着这条线走以循环方式(即，当你到达终点时，绕回起点，继续计数)扔掉每一个第九个元素，你最终会得到一个“喜爱”(1) 类别的元素

line = [1,1,1,1,0,0,0,0,0,1,1,0,1,1,1,...]

line (请参阅下面的游程编码元组版本)是实际的排序，如果你扔掉每九个，

line = [1,1,1,1,0,0,0,0,1,1,0,1,1,1,...] -- 9th thrown out

你总是会扔掉“不受欢迎的”0。如果从 RLE 元组的角度来看(其中 (0|1, n) 编码 n 连续出现的 0 或 1 )，从元组 (0,x) 中递减，即递减 x，最终会得到 (1,y) 元组，当然也会丢弃完全耗尽的 (0,0) 元组并重新压缩列表

line = [(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]

我已经开始了

tally = foldl (\acc elem -> if (snd(elem)+acc) >= 9
                            then (snd(elem)+acc)-9
                            else (snd(elem)+acc)) 0

当我喂它时线

tally [(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]

它获取第一个元组的 4，然后添加第二个元组的 5，获取 9 并重置累加器以启动再次“倒计时”。因此它准确地返回 3 ，这实际上是累加器在经过一轮并用第九个元组识别元组并重置累加器之后的剩余部分。我明显的问题是如何超越仅仅识别第九个元素，并实际开始递减0元组的元素，以及在它们减少到时将它们扔掉(0,0) 并重新运行。我确信将 line 构建为

会更容易

line = [1,1,1,1,0,0,0,0,0,1,1,0,1,1,1,...]

并再次开始卡住(即删除)第九个元素，它应该始终是 0 元素(例如，第一个第九个已从 line 中删除)

line = [1,1,1,1,0,0,0,0,1,1,0,1,1,1,...]

但这更像是一个挑战，因为我本质上需要将折叠与 map 结合起来——这就是我想要学习的，即纯功能性、无计数器等风格。感谢提示和帮助。另外，如果组合学领域的某人能够对这里发生的事情提供一些理论解释，那也很好。

Answer 1

寻找 map 和折叠可能会过度限制事情，因为这里有一个可爱的简单功能供您开始:

-- Remove the n-th element (zero-indexed) of a run-length encoded sequence of a.
chuck :: Int -> [(a, Int)] -> [(a, Int)]

扔掉空箱子；我们不应该在这里。

chuck _ [] = error "unexpected empty list"

让我们计算一下 chuck n ((a,m) : l) 。我们面临m相同的元素a ，我们要删除 n -th 元素。这取决于是否n < m (即搜索是否停止在这些 m 元素的中间，还是之后)。

如果n < m ，然后我们将删除其中之一 a 。我们还可以准备结果以预测下一个周期，该周期之后立即恢复a我们删除了。我们实际上已经跳过了n之前的其他元素，以及存储这些元素的好地方 n elements 是列表的末尾，因为无论如何我们都应该在末尾绕回。如果我们想计算圈数，我们需要更复杂的东西，但除非另有说明，YAGNI。还剩m-n-1元素，位于前面。小 helper rpt在我们尝试附加零个元素的情况下很有帮助。

otherwise ，我们跳过所有 m元素，将它们存储在后面，我们有 n-m还有更多工作要做。

chuck n ((a,m) : l)
  | n < m = rpt a (m-n-1) ++ l ++ rpt a n
  | otherwise = chuck (n-m) (l ++ [(a,m)])
  where rpt a 0 = []
        rpt a n = [(a,n)]

(注意:这会将 (a,m) 拆分为 (a,m-n-1) 和 (a,n) ，但不会将它们合并回来......留给读者作为练习。)

由于结果是为下一次迭代准备的，我们可以轻松链接 chuck看看线路的演变。请注意，在此实现中元素的索引为零，因此 chuck 8夹住“第九”元素。

ghci
> line
[(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]
> chuck 8 line
[(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1),(1,4),(0,4)]
> chuck 8 $ chuck 8 line
[(0,1),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1),(1,4),(0,4),(1,2),(0,1),(1,3),(0,1),(1,1)]

这有点难以理解。至少，我们应该确保只有0正在被抛弃。那么让我们来计算一下元素:

tally :: [(Int,Int)] -> (Int, Int)
tally xs = (sum (map snd (filter ((== 0) . fst) xs)), sum (map snd (filter ((== 1) . fst) xs)))

右侧的计数似乎保持不变，而错误的一侧则较少，正如预期的那样:

> tally line
(15,15)
> tally $ chuck 8 line
(14,15)
> tally $ chuck 8 $ chuck 8 line
(13,15)

通过 iterate 我们可以走得更快，它重复应用一个函数并在无限列表中返回所有中间结果:

> :t iterate
iterate :: (a -> a) -> a -> [a]

迭代chuck 8 ，统计起来，只查看我们期望停止的位置(删除一侧的所有 15 个元素后):

> take 16 $ map tally $ iterate (chuck 8) line
[(15,15),(14,15),(13,15),(12,15),(11,15),(10,15),(9,15),(8,15),(7,15),(6,15),(5,15),(4,15),(3,15),(2,15),(1,15),(0,15)]