Subset of length k?

Question

This following code works in an optimized way and i would like to understand it but failing. I understand first line but second line i get lost. If someone can explain it in C or Python that would be great or even general idea. Thank you

combinations :: Int -> [a] -> [[a]]
combinations k xs = combinations' (length xs) k xs
  where combinations' n k' l@(y:ys) 
    | k' == 0   = [[]] 
    | k' >= n   = [l] 
    | null l    = [] 
    | otherwise = map (y :) (combinations' (n - 1) (k' - 1) ys)

score 2 · Accepted Answer · answered Oct 07 '19 at 04:34

The equivalent in Python. Note that this very bad in CPython since recursion is so poorly implemented there, and pretty bad in all flavors of Python since lists aren't constructed the same way (1: [2, 3, 4]) is straightforward in Haskell, but doing the same in Python requires some dequeues or ugly [1] + [2,3,4] stuff)

from typing import TypeVar, List

A = TypeVar('A')
def combinations(k: int, xs: List[A]) -> List[List[A]]:
    def helper(n: int, k2: int, lst: List[A]) -> List[List[A]]:
        # base cases
        if k2 == 0: return [[]]     # if the requested subsequence length is zero
        elif k2 >= n: return [lst]  # if the requested subsequence length is longer than the whole sequence
        elif not lst: return []     # if the sequence itself is empty

        y, ys = lst[0], lst[1:]
        return [[y] + rest for rest in helper(n-1, k2-1, ys)]

    return helper(len(xs), k, xs)

Note that the overuse of guards in the Haskell strikes me as somewhat ugly. I would probably rewrite as:

combinations :: Int -> [a] -> [[a]]
combinations k xs = combinations' (length xs) k xs
  where
    combinations' _ 0  _  = [[]]
    combinations' _ _  [] = []
    combinations' n k' l@(y:ys)
      | k' >= n           = [l]
      | otherwise         = map (y :) (combinations' (n - 1) (k' - 1) ys)

Your answer also answer my question https://stackoverflow.com/questions/58262463/filter-subsets-based-on-length/58262504#58262504 , I'll mark it as duplicate, but if you want to add it there also, the bounty I think should be yours — developer_hatch, Oct 10 '19 at 18:09

score 0 · Answer 2 · answered Oct 10 '19 at 18:07

There is a simple alternative way equivalent with pattern matching provided by Khuldraeseth na'Barya in this question :

subsetsOfLength 0 _  = [[]]
subsetsOfLength _ [] = []
subsetsOfLength n (x:xs) = map (x:) (subsetsOfLength (n-1) xs) ++ subsetsOfLength n xs

Subset of length k?

2 Answers2