CODEWITHSUNDEEP
f#combinatorics
Stewart_R
Stewart_R

Reputation: 14485

Is there a library function in F# Combine elements from different lists

I want a function f that takes a list of lists and returns the list of tuples of all possible combinations made by taking one element from each list.

For example

f [["A";"B";"C"];[1;2]]

would give the result:

[("A",1);("A",2);("B",1);("B",2);("C",1);("C",2)]

and:

f [[onions;peas];[mash;fries];[chicken;steak]]

would give:

[(onions,mash,chicken);(onions,mash,steak);(onions;fries;chicken) ... (peas,fries,steak)]

I am contemplating rolling my own but feel like there MUST be a library function somewhere much better optimised than my thumb-fisted approach but I cannot seem to find anything by googling (I may not know the correct combinatoric term for this so keep hitting different combination methods & functions)

Upvotes: 4

Views: 626

Answers (3)

Ringil
Ringil

Reputation: 6537

Actually, CaringDev and Mark Seemann are not quite right. There isn't an library implementation yet, but there will be a Cartesian product implementation in F# 4.1 (Coming Soon TM): https://github.com/Microsoft/visualfsharp/pull/989. It can be used like this: 

List.allPairs ["A"; "B"; "C"] [1; 2]
//val it : (string * int) list =
//[("A", 1); ("A", 2); ("B", 1); ("B", 2); ("C", 1); ("C", 2)]

That said, it doesn't quite solve your problem because it only accepts two lists for its inputs, but extending it shouldn't be too difficult.

Upvotes: 4

Mark Seemann
Mark Seemann

Reputation: 233150

Like CaringDev, I don't think that there are any standard library functions that do this. One of the reasons, I think, is that they would have different types.

Code such as [["A";"B";"C"];[1;2]] from the OP doesn't even compile, because the use of string values indicates to the compiler that this is a nested list of strings, but [1;2] is a list of integers.

It can be done with tuples instead, but this is where a combinatorial function for a pair would be different from one for a triplet, and so on.

That said, such functions are trivial to implement:

let combine2 xs ys = [
    for x in xs do
    for y in ys do
    yield x, y ]

let combine3 xs ys zs = [
    for x in xs do
    for y in ys do
    for z in zs do
    yield x, y, z ]

Examples:

> combine2 ["A";"B";"C"] [1;2];;
val it : (string * int) list =
  [("A", 1); ("A", 2); ("B", 1); ("B", 2); ("C", 1); ("C", 2)]
> combine3 ["onions"; "peas"] ["mash"; "fries"] ["chicken"; "steak"];;
val it : (string * string * string) list =
  [("onions", "mash", "chicken"); ("onions", "mash", "steak");
   ("onions", "fries", "chicken"); ("onions", "fries", "steak");
   ("peas", "mash", "chicken"); ("peas", "mash", "steak");
   ("peas", "fries", "chicken"); ("peas", "fries", "steak")]

Upvotes: 7

CaringDev
CaringDev

Reputation: 8551

There is no implementation of the "Cartesian product" in F# standard libraries. Creating your own implementation (e.g. using list comprehensions) is perfectly fine.

Upvotes: 3

Related Questions