all subsets of length k

[Pietro Abate]

Hi all,

Say I want to generate all sublists of length k.
The naive way (code below) should be something along these
lines :

f X k = [ x | x <- (subsets X) ; |x| <= k ]
where subsets is a function that generates all sublists of X.

I've two questions: Is there a better (more efficient) way of doing this ?
Leave alone the fact that ocaml lists are not lazy, I don't think this is
the most efficient way to solve this problem as the subsets function
computes a lot of useless sets, for the sole reason of been discarded by the
other function. I can think of adding a parameter to the subsets function,
so to stop computing as soon the list gets bigger then k, but this will make
the algorithm more difficult to understand...

The other minor question is: can I write "all subsets of X" with the
list comprehension notation ?

thanks :)

-------------------------------------

let return a = [a]
let bind m f = List.flatten (List.map f m)
let mzero = []
let guard b = if b then return () else mzero
let card l = (List.length l)

let rec subsets = function
|[] -> return []
|h :: t ->
bind (subsets t) (fun t1 ->
mplus (
bind (return t1) (fun t2 -> return (h :: t2))
)
(return t1)
)
;;

(* f l k = [ x | x <- (subsets X) ; |x| <= k ] *)
let f l k =
bind (subsets l) (fun x ->
bind (guard (card(x) <= k)) (fun _ ->
return x
)
)
;;

--
++ Blog: http://blog.rsise.anu.edu.au/?q=pietro
++
++ "All great truths begin as blasphemies." -George Bernard Shaw
++ Please avoid sending me Word or PowerPoint attachments.
See http://www.fsf.org/philosophy/no-word-attachments.html

[ol...@pobox.com]

Pietro Abate wrote:
> Say I want to generate all sublists of length k

> Is there a better (more efficient) way doing this ?

Perhaps you would like a set of articles
`Deriving fast functions to compute all subsets of size N'
http://pobox.com/~oleg/ftp/Algorithms.html#subsets-n