Today’s entry is about generating permutations in both a functional and readable way.

No, these qualities are not at odds with each other. At least, they don’t have to be.

The example code today generates permutations where r = n. For example, given List(1,2,3) (n = 3, the size of the list) how many permutations of length 3 (r = 3 also) are there.

**The functional way using flatMap and Map**

def permute1(xs: List[Int]): List[List[Int]] = { if(xs.size < 2) { List(xs) } else { xs.flatMap(x => permute1(xs diff List(x)).map(y => x :: y)) } }

The output on List(1,2,3,4) is:

List(1, 2, 3, 4) List(1, 2, 4, 3) List(1, 3, 2, 4) List(1, 3, 4, 2) List(1, 4, 2, 3) List(1, 4, 3, 2) List(2, 1, 3, 4) List(2, 1, 4, 3) List(2, 3, 1, 4) List(2, 3, 4, 1) List(2, 4, 1, 3) List(2, 4, 3, 1) List(3, 1, 2, 4) List(3, 1, 4, 2) List(3, 2, 1, 4) List(3, 2, 4, 1) List(3, 4, 1, 2) List(3, 4, 2, 1) List(4, 1, 2, 3) List(4, 1, 3, 2) List(4, 2, 1, 3) List(4, 2, 3, 1) List(4, 3, 1, 2) List(4, 3, 2, 1)

The first thing to note is that this is an immutable implementation that doesn’t require any changing variables. This is a big improvement over a classic Java implementation with mutable state.

But as you may have noticed, readability suffers. Line 5 is kind of gnarly with a nested map statement inside a flatMap with multiple list operations and a recursive call:

def permute1(xs: List[Int]): List[List[Int]] = { if(xs.size < 2) { List(xs) } else { xs.flatMap(x => permute1(xs diff List(x)).map(y => x :: y)) } }

We can make this line slightly more readable by simply adding line breaks.

def permute1(xs: List[Int]): List[List[Int]] = { if(xs.size < 2) { List(xs) } else { xs.flatMap(x => permute1(xs diff List(x)) .map(y => x :: y ) ) } }

Still, that doesn’t help much in this case. At least, it doesn’t help me–flatMap permute map what??

*With for-comprehensions*

This is where I like the “for-comprehension” syntax that Scala provides. Our original line 5 can be rewritten as a for-comprehension like lines 5-8 here:

def permute2(xs: List[Int]): List[List[Int]] = { if(xs.size < 2) { List(xs) } else { for { x <- xs y <- permute2(xs diff List(x)) } yield x :: y } }

For most people I think this will be more intuitive. It makes some kind of intuitive sense that is confirmed once you read a bit about it.

If you run into a situation like our first bit of code above, where multiple flatMap and filter statements are being used, consider rewriting with a for-comprehension and see if it doesn't clarify the code a bit!

You can learn more for-comprehension syntax in chapter 16 of Programming in Scala. The syntax includes ways to filter and define variables.

One final note: a big problem with this function is that it is not tail recursive! Here's a challenge for you: rewrite it to be tail recursive!