按位置删除各种元素

Question

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

拥有一个包含

xs

不同元素的列表

n

。列表

n

的

xs

元素的组合从

m

到

m

（带有

m <= n

）是所有可能的

m

元素集合（没有重复），可以由原始

n

元素。

元素的顺序并不重要（这意味着

"abc"

被视为与

"bca"

相同的组合）。

例如：

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

定义一个函数

comb

，它接受一个自然数

m

和一个具有

xs

不同元素的列表

n

。

我能找到的唯一方法是我需要一个值来定位我的“位置指针”

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

基本上你可以做的就是每次选择一个元素并不断添加元素。

为了防止对称，我们可以说，如果我们在位置i处选择一个字符，我们只能选择位置i右侧的项目，因此这意味着我们将递归传递给位置i的

rest

列表中的字符。

我们可以首先构造一个辅助函数，对于给定的列表

[a]

，返回一个 2 元组

[(a, [a])]

 的列表，其中包含所选项目和其余项目，因此：

pick :: [a] -> [(a, [a])]
pick [] = []
pick (x : xs) = … : …

我留下填写

…

部分作为练习。对于

[1,4,2,5]

，它应该返回

[(1, [4,2,5]), (4, [2,5]), (2, [5]), (5, [])]

，因为我们可以选择任何元素，并且每次在我们选择的元素的右侧都有一个剩余元素列表，我们可以使用它来选择其他项目。 现在我们有了这个，我们可以创建一个递归函数来选择 n 元素。我们通过检查仍有多少商品需要挑选来做到这一点。对于没有项目，我们返回单个项目：空列表。对于 n 项，我们选择一个项并递归使用

n-1

 项：

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb n xs = [x : zs | (x, ys) <- pick xs, zs <- comb (n - 1) ys]

我们可以进一步提升这一点，只选择拾取后仍剩余

n-1

元素的元素。我也将其作为练习。 因此，我们这里不需要列表的长度，我们只需选择元素即可。如果初始列表具有无限长度，这甚至会产生结果：如果我们需要 m 项，它最终将返回 [x1_{, x}2_{, …, x}m-1_{, x}n _] 对于任何 n ≥ m，从而产生结果，尽管对于上述实现它永远不会产生以 [x1_{, x}3_{, …]} 开头的结果。