组合学：圣彼得博弈算法

Question

有一个组合数学难题（如 Jan Gullberg 在数学从数字的诞生 中提到的那样），如果您将来自两个类别的十五个成员排列成一行（例如，类别 [=15 个） =17=] 和类别 1 中的十五个，总共 30 个元素）以 特定顺序 混合，然后如果你连续沿着这条线走 以循环方式（即当你到达终点时绕回起点，继续计数）抛出每一个第9个元素，你最终将只包含“偏爱”(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

当我喂它时line

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 并重置累加器以再次开始“倒计时” .因此它准确地 returns 3 实际上，这是累加器在进行一次传递并用第九次识别元组并重置累加器之后的剩余部分。我明显的问题是如何超越识别第九个元素，并实际开始递减 0 元组的元素，以及在它们下降到时将它们扔掉(0,0) 并重新运行ning。我确定将 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,...]

但这更具挑战性，因为我本质上需要折叠与地图相结合——这正是我想要学习的，即纯功能性、无计数器等风格。提示和帮助表示赞赏。此外，如果组合学知识中的某个人可以从理论上阐明这里发生的事情，那也很好。

Answer 1

寻找地图和折叠可能会过度限制事物，因为这里有一个可爱的简单功能供您开始使用：

-- 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 个元素。这取决于 n < m（即搜索是在 m 元素的中间还是之后停止）。

如果n < m，那么我们将删除其中一个a。我们还可以为下一个周期准备结果，下一个周期在我们删除 a 之后立即恢复。我们实际上已经跳过了它之前的 n 个其他元素，存储这些 n 个元素的好地方是列表的末尾，因为无论如何我们都应该在末尾返回。如果我们想计算圈数，我们将需要更复杂的东西，但除非另有说明，YAGNI。剩下 m-n-1 个元素，留在前面。一个小帮手 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)，但不会将它们合并回来...留作 reader 的练习.)

由于结果是为下一次迭代准备的，我们可以轻松地链接 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 进行得更快，它重复应用一个函数并且 returns 所有中间结果都在一个无限列表中：

> :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)]

Answer 2

使用 RLE 会使事情复杂化。您只需要数数：

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)]
unRLE rle = [c | (c,n) <- rle, c <- replicate n c]
test = count9 1 (sum [n | (0,n) <- line]) -- 15 
                [] $ unRLE line

count9 _ 0 rev line   = reverse rev ++ line
count9 9 n rev (0:xs) = count9 1 (n-1) rev xs
 -- removing 1 is error:
count9 9 n rev (1:xs) = error "attempt to remove 1"
count9 i n rev (x:xs) = count9 (i+1) n (x:rev) xs
count9 i n rev []     = count9 i n [] (reverse rev)

运行它

> test
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

如果您想在每个 0 被移除时查看 line 的状态，您需要调整此项。

组合学：圣彼得博弈算法

Combinatorics: St. Peter's Game algorithm

haskell

combinatorics

fold

run-length-encoding

circular-list