scala-logo-small

Scala permutation generation shootout – for-comprehension vs. functional style

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!

Get CODE in your inbox

Yes email me when there are new posts

Leave a Reply

Your email address will not be published. Required fields are marked *