有人可以解释此排列生成代码背后的逻辑吗？

Question

Frnakly，对我来说看起来像黑魔法。当然，我对Haskell的了解相当有限，但我可以理解基本原则。仅仅因为它使我尝试通过测试输入工作变得容易得多，但是在这种情况下，这仍然没有意义。

背景： 大约一年前>关于我正在尝试的置换生成代码，积累了我的“重复置换”代码的递归呼叫，以堵塞RAM？）开始工作。我从这个奇妙的社区那里得到了很多帮助，并继续了我的项目。但是，我最近重新探讨的用户“彼得·普特”（Peter Pun）的最后一个答案是我当时没有太多想法的。

一部分答案，生成排列的重要一个是，这

permutationsNub :: Eq a => [a] -> [[a]]
permutationsNub = foldr (concatMap . insert) [[]]
    where insert y = foldr combine [[y]] . (zip <*> tail . tails) -- tails through importing Data.List
              where combine (x, xs) xss = (y : x : xs) :
                        if y == x then [] else map (x :) xss

使我能够以对我更有意义的方式改革该功能，以便我可以看到每个论点并参考它，因为原始应用中的部分应用使我困惑的可变名称。请告诉我解释是否正确。

permutationsNub :: Eq a => [a] -> [[[a]]]
permutationsNub digits = scanr (concatMap . insert) [[]] digits
    where insert digit perms = foldr combine [[digit]] $ (zip <*> tail . tails) perms -- zip will produce  tuples of the form (a, [a])
              where combine (permX, tailOfPerms) digitAsDoubleList = (digit : permX : tailOfPerms) : 
                      if digit == permX then [] else map (permX :) digitAsDoubleList

我用SCANR替换了Main FoldR函数（也是输出类型）以查看中间步骤，因此，如果我运行 permuntuntNub [2,7,7,7,8] 结果是 [[[[2,7,7,8]，[7,2,7,8]，[7,7,2,8]，[7,7,8,2]，[2,7，[2,7， 8,7]，[7,2,8,7]，[7,8,2,7]，[7,8,7,2]，[2,8， 7,7]，[8,2,7,7]，[8,7,2,7]，[8,7,7,2]，[[7,7,8]，[7,8，[7,8， 7]，[8,7,7]]，[7,8]，[8,7]]，[[8]]，[[]] 给出一些洞察力。

因此，我必须问：

1. 首先，为什么使用 zip> zip 的应用符号（＆lt;*＆gt; ）？它是由使用毫无用处符号所决定的吗？应用程序如何渗入？

2. 我对变量的重命名，使它们对我来说很有意义，因为功能有效，又名与原始输出相同。但是，有些事情很奇怪，例如 Digit 如何根据组合函数在比较检查中等于 permx ？前者是int，后者是[int]，否则像 digit：permx：... 在同一函数中无法使用，对吗？例如，如果我们调用 permuntunnub [2,7,7,8] ，在主foldr（或scanr）函数的第二遍中，数字将为 7 和permx将 [8] ，那么这两个如何相等？

3. 从这里变得陌生。好吧，他们俩都可以被束缚到尾流，这是一个[[int]]，但是在括号中封闭的整个事情都与... [[int]]有关？再次？

实际上， map（permx :) digitasdoublelist 似乎不起作用（但是，它以某种方式确实...），因为我们正在尝试将[int]映射到[[int]]，例如是结果，然后是先前的[[int]]的缺点，我看不出它是如何适合的。 例如，在 permuntuarnnub的第二次通过，将7个作为下一个数字，由主foldr/scanr函数选中， insert的第一个通过将为（7：[8]：[] ）：[[8]：[[7]]，我无法理解。

4. 注意：如A 更高级别说明代码的作者所说的基本思想是，鉴于列表的尾巴的唯一排列，我们可以通过插入来计算整个列表的唯一排列它进入所有尾巴的排列，在不遵循头部出现的每个位置（避免创建重复）。因此，例如，假设尾巴的当前排列 是[[7,8]，[8,7]（请参见Pass 2），下一个数字为7。因此，算法将在第一个置换开始时插入7（生成[7,7,8]，然后在最后（生产[7,8,7]，然后仅在第二个排列开始时（生产[8,7,7]）？它怎么能说出它不需要其他地方？作者的含义是 遵循头部的位置？

没有

Answer 1

该算法只是基于经典的插入的修改，例如，您可以在。令我惊讶的是，尽管它很简单，但我无法在任何地方找到它。

首先，对于插入，我没有使用明确的递归（被认为有害），而是笨拙地模拟了列表。然后，我发现，如果我们在发现要插入的值后停止产生插入，我们可以防止创建重复项，同时又产生每个置换量。我希望以下代码阐明了事情：

parafoldr :: ((a, [a]) -> b -> b) -> b -> [a] -> b
parafoldr f y xs = foldr f y $ zip xs $ tail $ tails xs

insertions :: a -> [a] -> [[a]]
insertions y = parafoldr combine [[y]]
    where combine (x, xs) xss = (y : x : xs) : map (x :) xss
--or equivalently
insertions y xs = (y : xs) : (parafoldr combine [] xs)
    where combine (x, xs) xss = (x : y : xs) : map (x :) xss

permutations :: [a] -> [[a]]
permutations = foldr (concatMap . insertions) [[]]

insertions' :: Eq a => a -> [a] -> [[a]]
insertions' y = parafoldr combine [[y]]
    where combine (x, xs) xss = (y : x : xs) :
              if x == y then [] else map (x :) xss
--or equivalently
insertions' y xs = (y : xs) : (parafoldr combine [] xs)
    where combine (x, xs) xss
              | x == y    = []
              | otherwise = (x : y : xs) : map (x :) xss

permutationsNub :: Eq a => [a] -> [[a]]
permutationsNub = foldr (concatMap . insertions') [[]]

并不难显示：

• 通过诱导表明：置换的正确性， promistutionsnub 产生 code> promistations ， >生产，当然，没有其他列表
• 由 permututationsNub 产生的排列是成对的，

---

但实际上，我间接地到达了该算法。置换自然适合关系环境（请查看答案的结尾以获取参考文献）。在下文中，我使用非正式的伪哈斯尔表示法来写有关关系。我用 a〜＆gt表示； b 从 a 到 b 的关系类型。我写 r（x，y） <代码> r 将 x 与 y 相关联。在定义关系时，我认为定义的关系是满足给定条件的最少的关系。我用 relfoldr （ relunfoldr ）对列表和 Converse （猜猜是什么）相反操作的关系性血统（变形）的操作。

因此，请考虑以下关系：

• 排列:: [a]〜＆gt; [a] ; 置换（x，y）如果 y 是 x
• insertion :: lay（a，[a]）〜＆gt的 置换; [a] ; 插入（Nothing，[]）和插入（Just（X，XS），XS'）如果 XS'插入的结果x xs
• 插入'与插入相同的 某个地方 x xs 中的某个地方，但在发生它之后
• ” ＆gt;也许（a，[a]）; 选择（[]，nothing）和选择（xs，Just（x，xs'））如果 XS'删除出现的结果 x in xs
• 选择'与选择相同，但与“ XS'从删除 第一个 出现 x 在 xs 中的“

请注意 permuntion == Converse Demboint ， insertion == Converse Selection 和插入'== Converse Selection'。知道 relfoldr（Converse R）== Converse（RelunFoldr r），我大致进行了如下：

permutation ==
relfoldr insertion ==
converse (relunfoldr selection) ==
converse (relunfoldr selection') ==
relfoldr insertion'

已知第一个平等。由于置换的对称，我们具有置换== relunFoldr选择，这有助于我们证明 relunfoldr selection == relunfoldr选择'，因此第三平等。

现在，有了一些想象力，我们可以看到：

• relunfoldr选择提供了经典的基于选择的算法
• relunfoldr选择'提供了类似的基于选择的算法Create Replicates
• relfoldr插入给出了经典的基于插入的算法（命名 permututations 上面）
• relfoldr插入'给出了类似的基于插入的算法，该算法不会创建重复项（上面命名 permutationsnub 上面）

的一些优势，基于基于选择的基于选择的无限制算法是：

• 后者需要某种内存才能检查是否已经进行了选择，这使其效率较低，并且可能较低（取决于内存的类型，可能需要 ord ， hashable a 或 int 而不是 eq a ）
• 前者使用 foldr

在回答旧问题之前，我试图模拟 rel cpo 中的几件事，并在Haskell中实现它们，但我发现存在一些局限性和一个我需要的很多细节锻炼。我也有兴趣通过懒惰正确处理无穷大，但是我尝试过的一些技巧，例如对角/搭说，使用 nonepty 列表，我也不起作用，我也不确定适当的理论框架。如果我找到时间/能量/动机，我可能会在此领域进行一些时间重新访问该领域。

---

最后，这里有一些参考文献：

• 经典“ nofollow noreferrer”> bananas paper ）在 cpo 中。
• 该书“ nofollow noreferrer”>“ nofollow noreferrer”>代数专注于关系环境。在第130-131页中，它涉及排列并得出经典的基于插入的算法。
• 这本书 haskell的算法设计强调方程推理。排列在IT中具有独特的存在，并且均基于选择/插入的基本算法。
• 在讲义中，您可以找到一些相关事项的教学典范，“计划构建数学中的代数和煤炭方法”。 第5章采用功能方法（< strong> set ， cpo ）而第8章采用关系。

Answer 2

αfter几天，有些事情更有意义，我意识到我犯了两个错误。

第一个是关于和解值。无论出于何种原因，我都错误地认为连续值必须是连续的嵌套级别，例如：[b]：[[c]]，而仅适用于Cons Operator的最后一个值，例如A Cons Operator的最后一个值， ：b：c：[d]。

第二是，由于与辅助图不熟悉，我误解了插入函数。让我们假设（例如，如我的问题中提到的话，我们运行 permuntnub [2,7,7,8]”）
主折叠/scanr的第二次通过，那里的ACC现在被[[7,8]，[8,7]]填充（因为Scanr的使用向我们告知了我们）。使用ConcatMap意味着插入将应用于该ACC列表中的每个参数，而不是同时，而不是同时将映射函数的结果串联。因此，对于该特定的ACC内容，插入将两次执行，第一次将作为插入7 [7,8] ，第二次为 insert 7 [8,7] 。 在任何情况下都不是一旦插入7 [[7,8]，[8,7]] 。

这导致我再次改革整个功能

permutationsNub :: Eq a => [a] -> [[[a]]]
permutationsNub digits = scanr (concatMap . insert) [[]] digits 
    where insert digit permutationN = foldr combine [[digit]] $ (zip <*> tail . tails) permutationN 
              where combine (x, xs) accOfInsert = (digit : x : xs) : -- (x, xs) of permutationN e.g [7,[8]]
                      if digit == x then [] else map (x:) accOfInsert

之后，事情变得更加好。对于插入7 [7,8] zipping零件将产生 [（7，[8]），（8，[]）] 。之后，插入自己的foldr函数将一一选择这些元组，并在每个元组上调用 compine 。

例如，在同一执行过程中，联合收割机也将两次称为 combine（8，[]）[[7]）[[7]] ，并且一次为 combine（7，[[[[7，[ 8]）[[7,8,7]，[8,7]] （[[[7,8,7]，[8,7]]是第一个组合呼叫的结果，因此现在ACC在foldr循环中的值），它将导致[[7,7,8]。现在清楚地表明 digit 和 x 现在可以与 ints 相当，如果它们相同，则当前元素的尾巴置换将被忽略（被[]取代，在结束的第二次通过中发生。

同样，对于插入7 [8,7] [（8，[7]），（7，[[]）]，将联合收割称为 combine（7，[]）[[7]] and combine（8，8， [7]）[[7,7] ，这将导致[[7,8,7]，[8,7,7]

。 [[[7,7,8]，[[7,8,7]，[8,7,7]]将被串联为[[7,7,8]，[7,8,7]，[7,8,7]， ]。

[ 8,7,7 这算法是一种出色的方法，当然我无法提出自己的意思。置换生成代码。不过，仍然还没有完全掌握它。也许我错过了一些必要的理论背景ATM。哦，好吧...

我希望这对某人的情况有所帮助。不用说，对任何其他反馈/评论都得到了高度赞赏。

干杯!