How to convert a list of integers into a matrix of these integers in F#

Question

I am getting my F#eet wet and having a hard time getting my head around simple concepts. Please oblige me by helping with this question, NOT homework!

Say I have a list [1;2;3;4]

How do I transform it into list of all possible combinations of the list's elements:

[(1,2);(1,3);(1,4);(2,3);(2,4);(3,4)]?

What I have come up with:

 let tuples=
    let lst=[1;2;3;4]
    List.map (fun i->(i,i)) lst

Obviously this gives the wrong result, but how to proceed? Do I simply need to use the nested for loops approach that I would take writing this code in C#?

Answer 1

You could use recursion to achieve this, I believe this is called the "cons pattern"

open NUnit.Framework
open Swensen.Unquote

let convert input =
    let rec loop remain acc =
        match remain with
        | x :: xs -> 
            let combos = xs |> List.map (fun i -> (x,i))
            loop xs (acc@combos)
        | x -> acc

    loop input []

[<Test>]
let TheTest () =
    let actual = convert [1;2;3;4]
    let expected = [(1,2);(1,3);(1,4);(2,3);(2,4);(3,4)]
    test <@ expected = actual @>

Answer 2

The general idea would be this: for each element x of the list, produce a list of x-combinations by combining it with every element y that comes after x in the list.

To do this, you'd need to index the elements, so you can compare them in terms of coming before/after each other. For this you can use the List.indexed function:

let lst = [1;2;3;4]
let indexedLst = List.indexed lst
// indexedLst = [(0,1); (1,2); (2,3); (3,4)]

After we have the elements indexed, we can pick one element (together with its index) and produce a list of combinations of that element with every other element that comes after it:

let combineWithSuccessors (x_idx, x) = 
   [ for y_idx, y in indexedLst do 
       if y_idx > x_idx then yield (x, y) ]

// Or if you prefer not using list comprehensions:
let combineWithSuccessors (x_idx, x) = 
   indexedLst 
   |> List.filter (fun (y_idx, _) -> y_idx > x_idx)
   |> List.map (fun (_, y) -> (x, y))

// test it out:
combineWithSuccessors (2, 3) == [(3,4)]
combineWithSuccessors (0, 1) == [(1,2); (2,3); (3,4)]

Finally, generate such combinations list for every x, and concatenate all these lists in one:

let allCombinations = 
   indexedLst |> List.map combineWithSuccessors |> List.concat

And then put it all together:

let allCombinations lst =
    let indexedLst = List.indexed lst

    let combineWithSuccessors (x_idx, x) = 
        [ for y_idx, y in indexedLst do 
            if y_idx > x_idx then yield (x, y) ]

    indexedLst |> List.map combineWithSuccessors |> List.concat

Test it out:

allCombinations [1;2;3;4;5]
> [(1, 2); (1, 3); (1, 4); (1, 5); (2, 3); (2, 4); (2, 5); (3, 4); (3, 5); (4, 5)]

allCombinations [5;7;1;2;3]
> [(5, 7); (5, 1); (5, 2); (5, 3); (7, 1); (7, 2); (7, 3); (1, 2); (1, 3); (2, 3)]

Answer 3

Here is one solution using library functions:

let tuples xs =
    let ys = List.distinct xs
    ys
    |> List.allPairs ys
    |> List.filter (fun (x, y) -> x < y)
[1..4] |> tuples
// val it : (int * int) list = [(1, 2); (1, 3); (1, 4); (2, 3); (2, 4); (3, 4)]

Here is another solution based on list comprehensions:

let tuples' (xs: 'T list) =
    let ys = List.distinct xs
    let len1 = ys.Length - 1
    [for i in 0 .. len1 do for j in (i+1) .. len1 do yield (ys.[i], ys.[j])]
[1..4] |> tuples'
val it : (int * int) list = [(1, 2); (1, 3); (1, 4); (2, 3); (2, 4); (3, 4)]

(The type annotation is needed)

Answer 4

Cool so many solutions for the same problem, guess I will share mine

let combineInts (ar : int list) = 
    let rec combine head (tail: int list) (remain: int list) =
        if tail.Length > 1 then
            (head, List.head tail) :: (combine head tail.Tail remain)
        else if remain.Length > 1 then
            (head, tail.Head) :: combine remain.Head remain.Tail remain.Tail
        else
            [(head, tail.Head)] 
    combine ar.Head ar.Tail ar.Tail

Not a big fan of

(head, List.head tail) :: combine head tail.Tail remain

So

let combineInts (ar : int list) = 
    let rec combine head (tail: int list) (remain: int list) (combinedSoFar: (int*int) list) =
        if tail.Length > 1 then
            combine head tail.Tail remain (combinedSoFar @ [(head, tail.Head)])
        else if remain.Length > 1 then
            combine remain.Head remain.Tail remain.Tail (combinedSoFar @ [(head, tail.Head)])
        else
            combinedSoFar @ [(head, tail.Head)]
    combine ar.Head ar.Tail ar.Tail []