Combinatorial Search

For-comprehension

For example, we want to generate pairs:

• A pair has 2 element. e.g. (i, j)
• 0 < i < 5 and 0 < j < 5

First, we generate the Seq.

val pairs = (1 until 4)
  .map(i => (1 until 4).map(j => (j, i))
)

// Vector(Vector((1,1), (2,1), (3,1)), Vector((1,2), (2,2), (3,2)), Vector((1,3), (2,3), (3,3)))

Then, we flatten the Seq.

val flattenedPairs = pairs.flatten

// Vector((1,1), (2,1), (3,1), (1,2), (2,2), (3,2), (1,3), (2,3), (3,3))

xs.flatmap(f) = xs.map(f).flatten

So, the flattenedPairs can be generated by:

val flattenedPairs = (1 until 4)
  .flatMap(i => (1 until 4).map(j => (j, i))
)

Finally, we filter it.

val flattenedPairs = (1 until 4)
  .flatMap(i => (1 until 4).map(j => (j, i)))
  .filter(p => p._1 + p._2 > 4)

// Vector((3,2), (2,3), (3,3))

As we can see, it's very difficult to understand. Scala provides an easy way to write it.

for s yield e

• s: It's a squence of generators, e.g. map, and filters, e.g. filter.
• e: Expression whose value is returned by an iteration

val flattenedPairs = for {
  i <- 1 until 4
  j <- 1 until 4
  if (i + j) > 4
 } yield (j, i)

// Vector((3,2), (2,3), (3,3))