Skip to main content
 首页 » 编程设计

haskell之在 Haskell 中编写一个函数来获取大小为 n 的所有子序列

2024年06月20日152kerrycode

我试图编写一个函数来获取大小为 n 的列表的所有子序列,但我不知道如何去做。

我想我可能可以使用内置的 Data.List.subsequences 并过滤掉大小不是 n 的列表,但这似乎是一种相当迂回且低效的方法,而且我'如果可以避免的话我宁愿不这样做,所以我想知道你有什么想法吗?

我希望它是这样的类型

subseqofsize :: Int -> [a] -> [[a]] 

为了进一步说明,这是我正在寻找的示例:

subseqofsize 2 [1,2,3,3] 
[[1,2],[1,3],[2,3],[1,3],[2,3],[3,3]] 

此外,我不关心任何事情的顺序。

请您参考如下方法:

我假设这是家庭作业,或者您这样做是为了学习练习,所以我会给您一个解决方案的概述,而不是用勺子给您灌输正确的答案。

无论如何,这是一个递归问题。

两种基本情况:

sublistofsize 0 _        = ... 
sublistofsize _ []       = ... 

然后有两个递归步骤:

sublistofsize n (x : xs) = sublistsThatStartWithX ++ sublistsThatDon'tStartWithX 
  where sublistsThatStartWithX = ... 
        sublistsThatDon'tStartWithX = ... 

请记住,基本情况的定义需要与递归情况中的定义适当配合。仔细思考:不要仅仅假设基本情况都会导致空列表。

这有帮助吗?