按位置删除各种元素

Question

我正在为课堂做一个练习，经过一段时间的思考，我找到了理论上的方法，但无法弄清楚在 Haskell 中的方法。
练习是：

xs有一个包含不同元素的列表n。从到的n列表元素的组合（与）是可以从原始元素形成的所有可能的元素集（没有重复） 。xsmmm <= nmn

元素的顺序并不重要（这意味着"abc"被视为与 相同的组合"bca"）。

例如：

comb 0 "abcd" -> [""]
comb 3 "bcd" -> ["bcd"]
comb 2 "bcd" -> ["cd","bd","bc"]
comb 3 "abcd" -> ["bcd", "acd", "abd", "abc"]

定义一个函数comb，该函数接受一个自然数和一个包含不同元素的m列表。xsn

我能找到的唯一方法是我需要一个值来表示我的“位置指针” pp，这样它将删除length xs - m该指针之后的元素，然后在递归调用中删除元素m + pp，因此它“跳转”到下一个位置。我将以一种伪 Haskell 方式编写一个示例：

m = 3   xs = "abcd"   * = pp

*abcd       *remove (length xs - m) after pointer
Solution:  "bcd"  

*Recursively jump pointer by (length xs - m):

"a*bcd"   ->   "acd"
"ab*cd"   ->   "abd"
"abc*d"   ->   "abc"
"abcd*"   ->   [""]

我对这种发明感到非常抱歉，我尝试使用指针类比，因为我认为这样很容易看到它，并且我使用了伪代码和 Haskell 的混合，因为不知道该怎么做其他方式。

Answer 1

如何n从列表中选取元素？

comb :: Int -> [a] -> [[a]]

如果n为零，则无论列表是什么，您都只能选择一个其中没有元素的选项。

comb 0 _ = [[]]

否则，如果您的列表为空，则您根本没有选择。（注意这与上面的有何不同。）

comb _ [] = []

否则，你的列表就有头有尾。选秀如下。首先，您拥有包含头部的所有选秀权，然后拥有不包括头部的所有选秀权。

comb n (x:xs) = withHead ++ withoutHead where

如何构建排除头部的所有选秀权？这很简单，只需将函数递归地应用到列表的尾部即可。

    withoutHead = comb n xs

那么包含头部的选秀权又如何呢？这也很简单，只需将函数递归地应用于列表的尾部，但这一次使选择的元素更短。然后将头拍打在每个镐的前面。

    withHead = map (x:) (comb (n-1) xs)