Back to Questions
7.1k
views7
comments
0
score		+
-
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 :)

.Reply
Hide this comment

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 ()Reply
Hide this comment

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 ()Reply
Hide this comment

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 ()Reply
Hide this comment

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 ()Reply
Hide this comment

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 ()Reply
Hide this comment

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 ()Reply
Hide this comment

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 ()Reply

    Topic tags

    See all 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

    Logging in...