Back to Questions
4.8k
views7
comments
Best F# Idiom for Cartesian Product of a List of Lists
f#pipeline

I'm interested in the Cartesian Product of 'a list list

e.g. cprod [[1; 2]; [3; 4; 5]] => [[1; 3]; [1; 4]; [1; 5]; [2; 3]; [2; 4]; [2; 5]]

Being an amateur Schemer, my first working attempt was a direct translation from some Scheme code - with addition of pattern matching doing some of the work:

1
2
3
4

let rec cprod lol =
    match lol with
    | [] -> [[]]
    | x::xs -> List.map_concat (fun h -> List.map (fun t -> h::t) (cprod xs)) x

My next attempt is certainly more F#ish, but I have no idea whether it is the F# equivalent of 'Pythonic'. Is using pipeline here sensible when there isn't really a load of piping going on? It does seem to aid readability though?

1
2
3
4

let rec cprod lol =
    match lol with
    | [] -> [[]]
    | x::xs -> x |> List.map_concat (fun h -> cprod xs |> List.map (fun t -> h::t))

I'll be mapping this function over some thousands of individual int list list in order to uncompress a kind of compression scheme.

I don't have a clue about efficiency issues, too... so any suggestions would be helpful.

Does anyone know of a good source for F# or OCaml combinatorics code samples? I'm going to need k_subsets, k_permutations, + a few others later. No doubt I'll be able to translate Python and Scheme versions I already have, but a nice big collection of potted solutions would be very handy indeed.

Really Dumb Question: How do I get indenting to work here? -- this part solved :)

.

Hi,
using sequence expressions (as in the sample from James) makes many constructs like this quite simple, but it definitely takes some time to learn how to use them - and this is quite unique F# feature, so it's unfortunatelly hard to find samples in other languages that you could just rewrite.

Anyway, I implemented a function for calculating permuations here, so it may help:
[link:stackoverflow.com]

T.

By on 12/11/2008 6:00 PM ()

Below is a version using sequence comprehensions. If your input sequences are arrays then writing a nested-loop array specific version may be faster...

1
2
3
4
5

// "Extend" Seq module with a product
module Seq =
    let product xs ys = { for x in xs do for y in ys do yield x,y }

For F# code highlighting mark-up / quotation in hubfs forums, see here:[link:cs.hubfs.net]

By on 12/11/2008 11:55 AM ()

Use of some form of comprehension did occur to me because I do quite a lot of work in Python. The problem is that I do not have input data consisting of two sequences of something. My data looks like an arbitrary number of sequences which need to be CP'd out, e.g. 

1

 [[1; 2]; [3; 4; 5]; [6; 13]; [7; 8; 9; 10; 11]]

Thanks for the code markup hint. I'll go back and tidy mine up.

The permutations example will be useful for getting started - I'll need to modify it to handle k-permutations. The domain I work in is just full of things composed of k-permutations and k-subsets... e.g. quite often I need to generate the cartesian product of three sets of all 3-subsets of three input sets. Is there something like the Python Cookbook website for F# where people contribute snippets and debate them?

By on 12/11/2008 6:48 PM ()

Hello,

In case you just need .net implementation of combinatorics functions you can see to Iridium project
(MathNet.Numerics.Combinatorics class)

By on 12/12/2008 1:06 AM ()

The product of (n+1) sets can be written in terms of the product of n sets. That allows the enumeration to be written recursively.

1
2
3
4
5
6
7
8
9
10
11

/// Given a list of sets (sequences) [x1s;x2s;etcs...]
/// Return the product containing [x1;x2;etc...] for x1 in x1s, x2 in x2s, ...
//
//  The recursive step follows:
//     x1s * x2s * x3s * ... = x1s * (x2s * x3s * ...)
let rec products xss =
    match xss with
    | []                  -> seq { yield [] }
    | x1s :: x2s_x3s_etcs -> seq { for x1 in x1s do
                                   for x23etc in products x2s_x3s_etcs do
                                   yield x1 :: x23etc }
By on 12/12/2008 5:16 AM ()

and here is another version...

1
2
3
4
5
6
7
8
9

let cons (x,xs) = x::xs
let product2 xs ys = seq { for x in xs do for y in ys do yield x,y }
let rec productN xs = 
    match xs with
    | []        -> seq { yield [] }
    | xs :: xss -> product2 xs (productN xss) |> Seq.map cons

productN [[1;2];[3;4];[5;6]] |> Seq.to_array // arrays show more than seqs
By on 12/12/2008 5:18 AM ()

Thanks. I'm certainly going to be better off with your lazy versions given some of my expected input sizes and space considerations.

Iridium looks like a good source for Combinatorics functions although I'll probably want to work through these in F# and post my questions here - because (1) it's educational and (2) it's good to get this kind of thing online where it can be googled by others.

By on 12/12/2008 7:27 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