Haskell 中不相交循环的排列

Question

我试图在不使用 Monad 的情况下对 Haskell 中的循环实施排列。问题如下：给定数字 [1..n] 的排列，输出对应的不相交循环。函数定义为

permToCycles :: [Int] -> [[Int]]

对于输入：

permToCycles [3,5,4,1,2]

输出应该是

[[3,4,1],[5,2]]

根据循环置换的定义，算法本身很简单。由于 [3,5,4,1,2] 是 [1,2,3,4,5] 的排列，我们从第一个元素 3 开始，沿着轨道直到我们回到 3。在这个例子中，我们有两个循环 3 -> 4 -> 1 -> 3。继续这样做，直到遍历所有元素。因此输出为 [[3,4,1],[5,2]].

使用这个想法，在任何命令式语言中实现起来都相当容易，但我在Haskell中实现起来有困难。我在模块Math.Combinat.Permutations中找到了类似的东西，但是函数permutationToDisjointCycles的实现使用了Monad，我是初学者，这不太容易理解。

我想知道我是否可以在没有 Monad 的情况下实现它。感谢您的帮助。

更新：这是 Python 中实现的功能。

def permToCycles(perm):
    pi_dict = {i+1: perm[i]
               for i in range(len(perm))}  # permutation as a dictionary
    cycles = []

    while pi_dict:
        first_index = next(iter(pi_dict))  # take the first key
        this_elem = pi_dict[first_index]  # the first element in perm
        next_elem = pi_dict[this_elem]  # next element according to the orbit

        cycle = []
        while True:
            cycle.append(this_elem)
            # delete the item in the dict when adding to cycle
            del pi_dict[this_elem]
            this_elem = next_elem
            if next_elem in pi_dict:
                # continue the cycle
                next_elem = pi_dict[next_elem]
            else:
                # end the cycle
                break

        cycles.append(cycle)

    return cycles

print(permToCycles([3, 5, 4, 1, 2]))

输出为

[[3,4,1],[5,2]]

我认为在 Haskell 中实现它的主要障碍是如何跟踪标记（或未标记）的元素。在 Python 中，可以使用上面显示的字典轻松完成。同样在函数式编程中，我们倾向于使用递归来代替循环，但是这里我对这个问题的递归结构思考起来很费劲

Answer 1

让我们从基础开始。希望您从这样的事情开始：

permutationToDisjointCycles :: [Int] -> [[Int]]
permutationToDisjointCycles perm = ...

我们实际上并不想在输入列表中重复出现，因为我们想使用索引计数器。在这种情况下，我们需要一个递归辅助函数，下一步就是继续调用它，提供您认为需要的任何参数。这样的事情怎么样：

permutationToDisjointCycles perm = cycles [] 0
  where
    cycles :: [Int] -> Int -> [[Int]]
    cycles seen ix = ...

不像在Python中那样声明一个pi_dict变量，我们将从一个seen列表作为参数开始（我翻转它以跟踪所看到的内容，因为这最终会更容易一些）。我们对计数索引做同样的事情，我在这里称之为 ix。让我们考虑案例：

    cycles seen ix
      | ix >= length perm = -- we've reached the end of the list
      | ix `elem` seen    = -- we've already seen this index
      | otherwise         = -- we need to generate a cycle.

最后一个案例很有趣，对应于 Python 代码的内部 while 循环。您猜对了，另一个 while 循环意味着更多的递归！让我们编写另一个我们认为有用的函数，将 Python:

中的变量作为参数传递

      | otherwise         = let c = makeCycle ix ix in c : cycles (c ++ seen) (ix+1)

    makeCycle :: Int -> Int -> [Int]
    makeCycle startIx currentIx = ...

因为它是递归的，所以我们需要一个基本情况和递归情况（对应于 Python 代码中的 if 语句，它要么中断循环，要么继续循环）。与其使用 seen 列表，不如检查下一个元素是否等于起始索引更简单：

    makeCycle startIx currentIx =
      if next == start
      then -- base case
      else -- recursive call, where we attach an index onto the cycle and recur
      where next = perm !! i

我留下了几个需要填补的漏洞作为练习，这个版本适用于 0 索引列表而不是像你的示例那样的 1 索引列表，但算法的一般形状就在那里。

附带说明一下，上述算法效率不高。它对输入列表和“已见”列表都使用列表，列表中的查找总是 O(n) 时间。一个非常简单的性能改进是立即将输入列表 perm 转换为具有恒定时间查找的 array/vector，然后在最后使用它而不是 perm !! i。

下一个改进是将“已看到”列表更改为更有效的内容。为了匹配您的 Python 代码的想法，您可以将其更改为 a Set （或者甚至是 HashSet），它具有对数时间查找（或具有哈希集的常量）。

您找到的代码 Math.Combinat.Permutations 实际上使用布尔数组作为“已见”列表，然后使用 ST monad 在该数组上进行类似命令式的修改。这可能比使用 Set 或 HashSet 更快，但正如您自己所说，代码的可读性会受到一些影响。

Haskell 中不相交循环的排列

Permutation to disjoint cycles in Haskell

haskell

functional-programming

permutation

circular-permutations