2

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.

Michael Holman
  • 901
  • 1
  • 10
  • 26
  • 4
    Terminology nitpick: The term "sublist" usually means something different than "subsequence", i.e. a sublist only contains consecutive elements of the original list. So your function should be called `subsequencesOfSize`. – sepp2k Mar 29 '12 at 10:10
  • I will be using this function as part of a homework assignment, but it isn't directly the assignment. Part of my assignment is to score cribbage hands and I want to do this to help me score pairs. – Michael Holman Mar 29 '12 at 17:16
  • 1
    @MichaelHolman: Checking for pairs is easier and more efficient if you sort the list of cards first. Then you only have to compare adjacent cards. – hammar Mar 29 '12 at 17:39
  • @hammar Good call. I thought about doing it that way last night, but for some reason I thought it would be tough to deal with. I think at that point I was under the impression that only one pair/three of a kind/four of a kind was to be scored. Anyway, I went that route now and it is much simpler. – Michael Holman Mar 29 '12 at 18:18

2 Answers2

12

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?

dave4420
  • 46,404
  • 6
  • 118
  • 152
2

You can think about this mathematically: to compute the sublists of size k, we can look at one element x of the list; either the sublists contain x, or they don't. In the former case, the sublist consists of x and then k-1 elements chosen from the remaining elements. In the latter case, the sublists consist of k elements chosen from the elements that aren't x. This lends itself to a (fairly) simple recursive definition.

(There are very very strong similarities to the recursive formula for binomial coefficients, which is expected.)

(Edit: removed code, per dave4420's reasons :) )

huon
  • 94,605
  • 21
  • 231
  • 225