##
Solving Combinatoric Problems with List Comprehensions
*10 May 2015*

*Posted by Oliver Mason in algorithm, erlang.*

Tags: erlang, list comprehensions, maths

add a comment

Tags: erlang, list comprehensions, maths

add a comment

My daughter had some maths homework the other day:

You have 4 bags, each full of the numbers 1, 3, 5, and 7 respectively. Take 10 of the numbers that when added up make 37. What numbers are they?

So far so good: that sounds easy enough. But a bit of trial and error quickly leads nowhere. Something can’t be right. So, let’s get the computer to work it out.

As I haven’t done much Erlang recently I thought I’d give it a go. And, during a casual glance at Armstrong’s *Programming in Erlang* I thought I’d finally understood list comprehensions, so I wrote the following program:

`-module(comb).`

-export([result/0]).

result() ->

[{A+B+C+D+E+F+G+H+I+J,A,B,C,D,E,F,G,H,I,J}||

A <- [1,3,5,7],

B <- [1,3,5,7],

C <- [1,3,5,7],

D <- [1,3,5,7],

E <- [1,3,5,7],

F <- [1,3,5,7],

G <- [1,3,5,7],

H <- [1,3,5,7],

I <- [1,3,5,7],

J <- [1,3,5,7],

A+B+C+D+E+F+G+H+I+J =:= 37].

I declare a module with one function, `result/0`. This finds me ten variables that can take any of the four specified values and add up to 37. Simples!

The list comprehension has ten generators, and one filter; it will return a tuple with the sum and the individual variables’ values.

`Erlang R16B01 (erts-5.10.2) [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]`

Eshell V5.10.2 (abort with ^G)

1> comb:result().

[]

2>

WTF???! An empty list?! So I try changing the 37 to another value, like 36.

`3> comb:result().`

[{36,1,1,1,1,1,3,7,7,7,7},

{36,1,1,1,1,1,5,5,7,7,7},

{36,1,1,1,1,1,5,7,5,7,7},

{36,1,1,1,1,1,5,7,7,5,7},

{36,1,1,1,1,1,5,7,7,7,5},

[etc, etc].

So it does work! Only, there doesn’t seem to be an answer to the question. And with a bit of logical reasoning it is obvious: when adding two odd numbers, you get an even number. So adding ten odd numbers also yields an even number, but **37 is odd**.

*What I learnt from this exercise*: thinking about the problem beforehand can save you time, as there was no need to write a program at all. But then, I did get to use list comprehensions, and have learnt how powerful they are. And it neatly shows Erlang’s Prolog roots as well.