Back to Questions
1.2k
views2
comments
Combinations of a list of lists
f#

Hello all,
I'm trying to write a function that produces all the combinations of a list of lists.

eg:
combin [[1;2];[3;4];[5;6]]

Would produce the sequence:
{ [1;3;5]; [1;3;6]; [1;4;5]; [1;4;6]; [2;3;5]; [2;3;6]; [2;4;5]; [2;4;6] }

So far I have:
let combin all =
let rec combin all al =
seq {
match all with
| [] -> yield al
| h::t -> h |> List.map (fun a -> combin t (al @ (a::[]))) }
combin all []

Which has the right type('a list list -> seq<'a list>), but contains a warning and produces an empty sequence. Can anyone help get this function off the ground?

Much thanks.

.

Use yield! to return a whole sequence from a seq expression. You first have to aggregate the results of your recursive calls, however. You can append a 

1

List.concat

or directly use collect, the combination of map and concat.

1
2
3
4
5
6
7

let combin all =
    let rec combin all al =
        seq {
            match all with
            | [] -> yield al
            | h::t -> yield! h |> Seq.collect (fun a -> combin t (al @ (a::[]))) }
    combin all []

Since your code won't call multiple yields in a single pass, only exactly one of those two, you don't even need the sequence comprehension. Also, x::[] is equivalent to [x].

1
2
3
4
5
6

let combin all =
    let rec combin all al =
        match all with
        | [] -> Seq.singleton al
        | h::t -> h |> Seq.collect (fun a -> combin t (al @ [a ]))
    combin all []

Here's my take, avoiding appending to the aggregate list:

1
2
3
4
5
6
7

let rec combin = function
| [] -> Seq.singleton []
| xs::xss ->
    seq {
        for comb in combin xss do
            for x in xs do
                yield x::comb }
By on 12/20/2009 1:56 PM ()

Awesome. I've never used the function keyword (at least properly).

The only thing I see with your implementation is it switches which list is more significant when building the results.
Switching the two for loops solves that though.

1
2
3
4
5
6
7

let rec combin = function
| [] -> Seq.singleton []
| xs::xss ->
    seq {
        for x in xs do
            for comb in combin xss do
                yield x::comb }

Thanks agains for the help.

By on 12/20/2009 4:06 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper