列表分区递归实现 [英] List partitioning implemented recursively
问题描述
我正在研究一个函数：
separate :: [ a] - >在列表中输入并输出该列表的所有分区的[[[a]]]
。
例如123变成：
1 | 2 | 3
12 | 3
1 | 23
13 | 2
132
我只能实现一个递归函数来创建 1 | 2 | 3 变体：
separate':: [a] - > [[a]]
separate'（r：rs）= [r]：separate'xs
> separate [1,2,3]
[[1] ，[2]，[3]]
我试图用递归创建其他变体。
您可以将此函数看作是为两个列表元素之间的每个位置选择是否在其中包含分割。因此，对于初学者来说，n元素列表应该有2 n-1 分区：您可以使用它作为对可能解决方案的快速完整性检查。
对非确定性进行建模的一个好方法是使用list monad（或者等价地使用列表解析），所以让我们这样做。
首先，我们来写这个类型和一个基本情况：
separate：[a] - > [[[a]]]
separate [] = [[]]
一个单独的方法来分离一个空列表：空列表本身，不可能分裂。现在，由于我们有一个元素和一个剩余元素的列表，我们需要确定的一件事是列出所有拆分方法的方法其余元素：
分开:: [a] - > [[[a]]]
separate [] = [[]]
separate（x：xs）= let recur =分隔xs
未定义 - TODO
这里是有趣的东西开始的地方。正如我所说的，您可以将其视为选择每个项目是否在其之后进行分割。两种选择意味着将两个列表连接在一起，所以让我们这样做：
separate：[a] - > [[[a]]]
separate [] = [[]]
separate（x：xs）= let recur =单独xs
split = undefined - TODO
noSplit = undefined - TODO
split ++ noSplit
现在，我们如何引入一个在项目 x 之后拆分？我们这样做，对于 recur 中的每个分区，在其前面添加 [x] 作为新分区：
separate：[a] - > [[[a]]]
separate [] = [[]]
separate（x：xs）= let recur =分开xs
split = do
分区< - 循环
返回$ [x]：分区
noSplit =未定义 - TODO
in split ++ noSplit
不分裂怎么办？很相似！对于 recur 中的每个分区，我们将 x 添加到第一个子分区的前面：
separate：[a] - > [[[a]]]
separate [] = [[]]
separate（x：xs）= let recur =分开xs
split = do
分区< -
返回$ [x]：分区
noSplit = do
（y：ys）< - recur
return $（x：y）：ys
in split ++ noSplit
然后，我们完成了：
* Temp>单独的123
[[1，2，3]，[1，23]，[12，3]，[123]]
I am a Haskell beginner and I have been experimenting with recursive functions.
I am working on a function:
separate :: [a] -> [[[a]]]
that takes in a list and outputs all of the partitions of that list.
For example 123 becomes:
1|2|3
12|3
1|23
13|2
132
I have only been able to implement a recursive function that creates the 1|2|3 variant:
separate' :: [a] -> [[a]]
separate' (r:rs) = [r]:separate' xs
>separate [1,2,3]
[[1],[2],[3]]
I am stuck with trying to create the other variants with recursion.
You can think of this function as choosing, for each place in between two list elements, whether to include a split there. So for starters, there should be 2n-1 partitions for an n-element list: you can use that as a quick sanity check on a possible solution.
One good way to model non-determinism is with the list monad (or equivalently with list comprehensions), so let's do it that way.
First, let's write the type and a base case:
separate :: [a] -> [[[a]]]
separate [] = [[]]
There is a single way to separate an empty list: the empty list itself, with no possibility of splits. Easy enough.
Now, given we have one element and a list of remaining elements, one thing we'll need for sure is a list of all the ways to split the remaining elements:
separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
in undefined -- TODO
Here's where the interesting stuff starts. As I said, you can view this as choosing, for each item, whether to put a split after it. Two choices means concatenating together two lists, so let's do that:
separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
split = undefined -- TODO
noSplit = undefined -- TODO
in split ++ noSplit
Now, how do we introduce a split after the item x? We do it by, for each partition in recur, adding [x] to the front of it as a new partition:
separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
split = do
partition <- recur
return $ [x] : partition
noSplit = undefined -- TODO
in split ++ noSplit
What about not splitting? Pretty similar! For each partition in recur, we add x to the front of the first sub-partition:
separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
split = do
partition <- recur
return $ [x] : partition
noSplit = do
(y:ys) <- recur
return $ (x:y):ys
in split ++ noSplit
And with that, we're done:
*Temp> separate "123"
[["1","2","3"],["1","23"],["12","3"],["123"]]
这篇关于列表分区递归实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
