编写一个函数来获取Haskell中所有大小为n的子序列？ [英] Writing a function to get all subsequences of size n in Haskell?

问题描述

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

我想我可以使用内置的Data.List.subsequences，只是筛选出大小不是n的列表，但它看起来像是一个相当迂回和低效的方式，我宁愿不要如果我可以避免这样做，那么我想知道你是否有任何想法？

我希望它是这样的类型

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

如需进一步说明，请参阅以下示例： / p>

  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 = ... 
  

请记住，基本情况的定义需要与递归案例中的定义。仔细想想：不要只假定基本情况都会产生空列表。

这有帮助吗？

I was trying to write a function to get all subsequences of a list that are of size n, but I'm not sure how to go about it.

I was thinking that I could probably use the built-in Data.List.subsequences and just filter out the lists that are not of size n, but it seems like a rather roundabout and inefficient way of doing it, and I'd rather not do that if I can avoid it, so I'm wondering if you have any ideas?

I want it to be something like this type

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

For further clarification, here's an example of what I'm looking for:

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

Also, I don't care about the order of anything.

解决方案

I'm assuming that this is homework, or that you are otherwise doing this as an exercise to learn, so I'll give you an outline of what the solution looks like instead of spoon-feeding you the correct answer.

Anyway, this is a recursion question.

There are two base cases:

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

Then there are two recursive steps:

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

Remember that the definitions of the base cases need to work appropriately with the definitions in the recursive cases. Think carefully: don't just assume that the base cases both result in an empty list.

Does this help?

这篇关于编写一个函数来获取Haskell中所有大小为n的子序列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！