Generating all possible arithmetic combinations

Recently, I read this very interesting blog post which talked about combining the 4 basic arithmetic operators (+, -, , /) with bunch of given numbers to generate an answer. For example, how can the numbers {1, 2, 3, 4} be combined with the 4 basic arithemetic operators to give the answer 24. One way is `(1 + 2 + 3) 4 = 24`. There are other ways as well. We can write a program that will generate all possible combinations. I decided to write my own version using F#. The program works relatively well.

type Node =
    | Number of float
    | Addition of (Node * Node)
    | Subtraction of (Node * Node)
    | Division of (Node * Node)
    | ProductList of Node list

type Nodelist = Node list

let combineProduct (n1: Node) (n2: Node) : Node =
    match (n1, n2) with
    | (Number 0.0, _) -> Number 0.0
    | (_, Number 0.0) -> Number 0.0
    | (ProductList p1, ProductList p2) -> ProductList (p1 @ p2)
    | (ProductList p1, p2) -> ProductList (p2 :: p1)
    | (p1, ProductList p2) -> ProductList (p1 :: p2)
    | (_, _) -> ProductList [n1; n2]

let combineDivision (top: Node) (bottom: Node) : Node =
    match (top, bottom) with
    | (_, Number 1.0) -> top
    | (_, _) -> Division (top, bottom)

let combineTwoNodes (n1: Node) (n2: Node) : Nodelist =
    [
        Addition (n1, n2)
        Subtraction (n1, n2)
        Subtraction (n2, n1)
        combineProduct n1 n2
        combineDivision n1 n2
        combineDivision n2 n1
    ]

let rec pickAtIndex (xs: 'T list) (index: int) : 'T * 'T list =
    match index with
    | 0 -> (List.head xs, List.tail xs)
    | _ ->
        let head = List.head xs
        let tail = List.tail xs
        let e, rest = pickAtIndex tail (index - 1)
        (e, head :: rest)

let rec permuteNodes (nodes: Nodelist) : Nodelist =
    match nodes with
    | [] -> []
    | [n] -> [n]
    | [a; b] -> combineTwoNodes a b
    | nodes ->
        let n = [1 .. (nodes.Length - 1)]
        let a = n |> List.map (pickAtIndex nodes)
        a |> List.collect (fun (x, y) -> (permuteNodes y) |> List.collect (combineTwoNodes x))

let encloseInBrackets str = "(" + str + ")"

let rec str (node: Node) : (string * float) =
    match node with
    | Number n -> (string n, n)
    | Addition (n1, n2) -> 
        let str1, value1 = str n1
        let str2, value2 = str n2
        (str1 + "+" + str2 |> encloseInBrackets, value1 + value2)
    | Subtraction (n1, n2) -> 
        let str1, value1 = str n1
        let str2, value2 = str n2
        (str1 + "-" + str2 |> encloseInBrackets, value1 - value2)
    | Division (n1, n2) ->
        let str1, value1 = str n1
        let str2, value2 = str n2
        (str1 + "/" + str2 |> encloseInBrackets, value1 / value2)
    | ProductList p ->
        let a = p |> List.map str
        let str = a |> List.map fst |> String.concat "*" |> encloseInBrackets
        let value = a |> List.map snd |> List.reduce (*)
        (str, value)

[1.0; 2.0; 3.0; 4.0]
    |> List.map Number
    |> permuteNodes
    |> List.map str 
    |> List.filter (fun (s, v) -> v = 24.0)
    |> List.map (fun (s, v) -> s + "=" + (string v))
    |> String.concat "\n"
    |> printfn "%s"

niloy / blog

Generating all possible arithmetic combinations #29