Combinatorics problem (collection)

Question
1

Hi there,

trying to wrap my head around a combinatorics problem:

val xs = Seq(Seq("a", "b"), Seq("c", "d", "e"))
val ys = ???

assert(ys == Seq(
  Seq("a", "c"), Seq("a", "d"), Seq("a", "e"), 
  Seq("b", "c"), Seq("b", "d"), Seq("b", "e")
))

what’s a correct and elegant way to define ys? Note that xs can have an arbitrary list of inner lists.

Here is a first step when xs.length == 2:

val ys = for {
  i1 <- xs(0)
  i2 <- xs(1)
} yield Seq(i1, i2)

// equivalent
val ys = xs(0).flatMap { i1 => xs(1).map(i2 => Seq(i1, i2)) }
1 Like
2

This works. Don’t know if the best solution:

val xs = Seq(Seq("a", "b"), Seq("c", "d", "e"), Seq("f", "g"))

def combo(rem: List[List[String]], acc: List[String]): List[List[String]] =
  rem match {
    case Nil => Nil
    
    case last :: Nil => 
      last.map { z => (z :: acc).reverse }
      
    case head :: tail =>
      head.flatMap { z => combo(tail, z :: acc) }
  }

val xsL = xs.map(_.toList).toList
val ys = combo(xsL, Nil) 

assert(ys == Seq(
  Seq("a", "c", "f"), Seq("a", "c", "g"),
  Seq("a", "d", "f"), Seq("a", "d", "g"),
  Seq("a", "e", "f"), Seq("a", "e", "g"),
  Seq("b", "c", "f"), Seq("b", "c", "g"),
  Seq("b", "d", "f"), Seq("b", "d", "g"),
  Seq("b", "e", "f"), Seq("b", "e", "g")
))
1 Like
3

I think the biggest problem is that it is not tail recursive. With a small modification you can improve this:

def combo(rem: List[List[String]]): List[List[String]] =

  @scala.annotation.tailrec
  def loop(remaining: List[List[String]], acc: List[List[String]]): List[List[String]] =
        
    def body(head: List[String], reverse: Boolean): List[List[String]] =
      for
        p <- acc
        z <- head
        l = z :: p 
      yield if reverse then l.reverse else l
          
    remaining match
      case Nil          => Nil
      case head :: Nil  => body(head,true)
      case head :: tail => loop(tail, body(head,false))

  loop(rem, List(Nil))

Further, it depends on what you mean by “best”. Time wise? Memory wise?

3 Likes
4

Here is my solution (hopefully I understood what you want to do correctly):

// standard cross product of two seqs
// not quite what we want, since what we want to do is add to an existing seq
// (unused, for comparaison only)
def cross[T](xs: Seq[T], ys: Seq[T]): Seq[Seq[T]] =
  for {
    x <- xs
    y <- ys
  } yield Seq(x, y)

// takes a partial answer, and "crosses it" with one more sequence
// example:
// acc = Seq(Seq("a"), Seq("b"))
// xs = Seq("1", "2")
// returns Seq(Seq("a", "1"), Seq("a", 2), Seq("b", "1"), Seq("b", 2))
def cross2[T](acc: Seq[Seq[T]], xs: Seq[T]): Seq[Seq[T]] =
  for {
    a: Seq[T] <- acc // example a = Seq("a")
    x: T <- xs       // example x = "2"
  } yield a :+ x     // example yield Seq("a", "2")


def metaCross[T](xss: Seq[Seq[T]]): Seq[Seq[T]] =
  // the "zero" must be Seq(Seq()), if it's just Seq(), it returns just that
  // I don't have a good intuition to give you, I usually just use some relevant "zero-y" values until it works
  // Example zero-y values in general: 0, 1, "", Seq(), Map(), Seq(Seq()), Seq(0), ...
  xss.foldLeft(Seq(Seq())){ 
    case (acc, xs) => // iterates over xss, extracting each xs, and accumulating into acc
      cross2(acc, xs)
  }

val xss = Seq(Seq("a", "b"), Seq("c", "d", "e"))
val yss = metaCross(xss)

assert(yss == Seq(
  Seq("a", "c"), Seq("a", "d"), Seq("a", "e"), 
  Seq("b", "c"), Seq("b", "d"), Seq("b", "e")
))

The key bit is foldLeft, it allows you to combine the elements of a sequence (or list, or …) using an operation:

Seq(1, 2, 3).foldLeft(0){ case (acc, elem) => acc + elem}
// equivalent to
((0 + 1) + 2) + 3

It’s very powerful and general, to the point I basically never need to deconstruct Lists !
I also recommend to give a look at scanLeft, for cases where you want to create intermediate outputs:

Seq(1, 2, 3).scanLeft(0){ case (acc, elem) => acc + elem}
// equivalent to
Seq(
  0
  0 + 1
  0 + 1 + 2
  0 + 1 + 2 + 3
)

(There’s also reduceLeft, but it’s not as powerful and is mostly for cases where a zero element doesn’t make sense for the operation you are doing)

4 Likes
5

There are some solutions at https://stackoverflow.com/questions/23425930/generating-all-possible-combinations-from-a-listlistint-in-scala

3 Likes
6

Thanks everyone. I completely forgot about Scastie (haven’t been here or used it in years), super!

7

For fun I tried to make a generic version, which would take a tuple of seqs, and return a seq of all the “cross product”-tuples:

(Seq("a", "b"), Seq(1, 2)): (Seq[String], Seq[Int])
// would output
Seq(("a", 1), ("a", 2), ("b", 1), ("b", 2)): Seq[(String, Int)]

Sadly I did not manage to, you can find my attempt below

Attempt 
// standard cross product of two seqs
// not quite what we want, since what we want to do is add to an existing tuple
// (unused, for comparaison only)
def cross[A, B](xs: Seq[A], ys: Seq[B]): Seq[(A, B)] =
  for {
    x <- xs
    y <- ys
  } yield (x, y)


def crossAcc[X, T <: Tuple](xs: Seq[X], acc: Seq[T]): Seq[X *: T] =
  for {
    x: X <- xs       // example x = "a"
    a: T <- acc      // example a = (2,) // technically Tuple1(2)
  } yield x *: a     // example yield ("a", 2): (String, Int)

type UnSeq[S <: Seq[?]] = S match
  case Seq[t] => t

type TupleOf[T] = EmptyTuple | T *: EmptyTuple | (T, T) | (T, T, T)

extension [T <: Tuple](t: T)
  def foldRight[Z](z: Z)[F[_, _]](f: [Elem, Acc] => (e: Elem, acc: Acc) => F[Elem, Acc]): Tuple.Fold[T, Z, F] =
    ???
  def foldRightSeq[Z](z: Z)[F[_, _]](f: [X, T <: Tuple] => (xs: Seq[X], acc: Seq[T]) => F[Seq[X], Seq[T]]): Tuple.Fold[T, Z, F] =
    ???

def metaCross[Ts <: TupleOf[Seq[?]]](xss: Ts):
  Tuple.Fold[Ts, Seq[Nothing] *: EmptyTuple, [Xs <: Seq[?], Ts >: Seq[Nothing] <: Seq[Tuple]] =>> Seq[UnSeq[Xs] *: UnSeq[Ts]]] =
    val zero: Seq[Nothing] *: EmptyTuple = Seq() *: EmptyTuple
    // I can't get this part to compile:
    xss.foldRightSeq(zero)[[Xs <: Seq[?], Ts >: Seq[Nothing] <: Seq[Tuple]] =>> Seq[UnSeq[Xs] *: UnSeq[Ts]]](
      [X, T <: Tuple] => (xs: Seq[X], acc: Seq[T]) => 
        crossAcc[X, T](xs, acc)
    )
  /*
  xss.foldRight(Seq() *: EmptyTuple)(
    [Xs <: Seq[?], Ts <: Seq[Tuple]] => (xs: Xs, acc: Ts) => 
      crossAcc[UnSeq[Xs], UnSeq[Ts]](xs, acc)
  )
  */


val xss = (Seq("a", "b"), Seq(1, 2))
val yss = metaCross(xss)

assert(yss == Seq(
  ("a", 1), ("a", 2), ("b", 1), ("b", 2)
))
2 Likes
8

BTW, the “best” solution in terms of memory consumption and time efficiency is usually with iterators and arrays. But that is, at the same time, also very non-Scala like. Something to hide away deep in your library :grin:

9

If you’re feeling especially fearless, here’s some, ‘
code I wrote in F# a while back that you could run through your friendly local LLM…

I couldn’t stop myself from calling the Cartesian product a ‘cross’ product and have been pulled up about it since, despite my studying mathematics and physics back in prehistory. :blush:

There is also a ‘decorrelated’ version there too.

1 Like
10

Hi @Sciss,

I had a first stab at using foldM:

import cats.implicits.*

def combine(xss: List[List[String]]): List[List[String]] =
  xss.foldM(List(List.empty[String])){(yss,xs) => 
    for
      x  <- xs
      ys <- yss    
    yield List(x :: ys)
  }.flatten.map(_.reverse)

val xss2 = List(List("a", "b"), List("c", "d", "e"))
val yss2 = combine(xss2)
assert(yss2 == List(
  List("a", "c"), List("a", "d"), List("a", "e"), 
  List("b", "c"), List("b", "d"), List("b", "e")
))

val xss3 = List(List("a", "b"), List("c", "d", "e"), List("f", "g"))
val yss3 = combine(xss3)
assert(yss3 == List(
  List("a", "c", "f"), List("a", "c", "g"),
  List("a", "d", "f"), List("a", "d", "g"),
  List("a", "e", "f"), List("a", "e", "g"),
  List("b", "c", "f"), List("b", "c", "g"),
  List("b", "d", "f"), List("b", "d", "g"),
  List("b", "e", "f"), List("b", "e", "g")  
))

val xss4 = List(List("a", "b"), List("c", "d", "e"), List("f", "g"), List("h", "i"))
val yss4 = combine(xss4)
assert(yss4 == List(
  List("a", "c", "f", "h"), List("a", "c", "f", "i"),
  List("a", "c", "g", "h"), List("a", "c", "g", "i"),
  List("a", "d", "f", "h"), List("a", "d", "f", "i"),
  List("a", "d", "g", "h"), List("a", "d", "g", "i"),
  List("a", "e", "f", "h"), List("a", "e", "f", "i"),
  List("a", "e", "g", "h"), List("a", "e", "g", "i"),
  List("b", "c", "f", "h"), List("b", "c", "f", "i"),
  List("b", "c", "g", "h"), List("b", "c", "g", "i"),  
  List("b", "d", "f", "h"), List("b", "d", "f", "i"),
  List("b", "d", "g", "h"), List("b", "d", "g", "i"),
  List("b", "e", "f", "h"), List("b", "e", "f", "i"),
  List("b", "e", "g", "h"), List("b", "e", "g", "i")    
))

Here is a scastie.

If you are new to foldM (I am not making any assumptions) and you are interested, maybe check out the following:

Combinatorial Interview Problems with Backtracking Solutions - from Procedural to Functional Programming - Part 1

Combinatorial Interview Problems with Backtracking Solutions - from Procedural to Functional Programming - Part 2

1 Like
11

@Sciss You can tell that I had not looked at other solutions yet, beyond realising that one of them used a fold.

Having just seen @Sporarum’s solution, my first thoughts are that unless I am missing something, in trying to use foldM, I ended up with the same approach as his, except that an ordinary fold is sufficient: no need for foldM!

Also, I used reverse instead of :+.

12

@Sciss yes, here is the same scastie after replacing foldM with foldLeft and replacing reverse with ys :+ x