Make List whose sublists cover all combinations of two input Lists

Question

I am trying to make combinations (Please let me know if the terminology that I am using can be improved), such that we every element of the result list is a combination of two input lists, and the result list covers all the possible combinations.

The elements are not allowed to move around, the the first element of a sublist is first element of either input List, the second element of a sublist is second element of either sublist, and so on..

Example 1:

Input: List(1,1,1) and List(0,0,0) (we can assume that lists have same length)

Output:

List(List(1, 1, 1),
 List(1, 1, 0),
 List(1, 0, 1),
 List(0, 1, 1),
 List(1, 0, 0),
 List(0, 1, 0),
 List(0, 0, 1),
 List(0, 0, 0))

Example 2:

Input: List(1,2,3) and List(4,5,6)

Output:

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

My current solution only works on the simple case (Example 1):

  def makeCombinations(a: List[Int], b: List[Int]): List[List[Int]] = {
    val N = a.length
    (0 to N).map(x => a.slice(x, N) ::: b.slice(0, x)).flatMap(x => x.permutations).toList

  }

What is the best way to approach this?

I am not looking to find a cross product, which would result in:

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

This questions is different from: Cross product in Scala

When you say "all possible combinations", are elements from the input lists allowed to move around are they? So would `List(1,2,3)` be in the output of combining `List(2,2,2)` and `List(3,3,1)`? What about reusing elements? Is `List(1,1,1)` in the output of `List(1,2,3)` and `List(4,5,6)`? — Alec, Jul 10 '17 at 16:55
@Alec, good point, no they are not allowed to move around (which invalidates my code for the the example I provided). I will update my question shortly. — Akavall, Jul 10 '17 at 17:00
Possible duplicate of [Cross product in Scala](https://stackoverflow.com/questions/14740199/cross-product-in-scala) — , Jul 10 '17 at 17:59
@Mika'il, I edited my question, I don't believe this is a duplicate. — Akavall, Jul 10 '17 at 18:09

score 4 · Answer 1 · answered Jul 10 '17 at 17:42

Here's one way to look at it: you want to zip together the input lists, then you want to walk the resulting list of tuples, flatMaping along the way to try all combinations. The way to do this efficiently on a List is using foldRight.

def combine[A](xs: List[A], ys: List[A]): List[List[A]] =
  (xs zip ys).foldRight(List(List[A]()))(
    (xy, zss) => for (z <- List(xy._1, xy._2); zs <- zss) yield (z :: zs)
  )

Trying it out at the REPL:

scala> Test.combine(List(1,2,3), List(4,5,6))
res0: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 6), List(1, 5, 3),
List(1, 5, 6), List(4, 2, 3), List(4, 2, 6), List(4, 5, 3), List(4, 5, 6))

In Haskell, this is much neater: `combine xs ys = foldr (\(x,y) zss -> (:) <$> [x,y] <*> zss) [[]] $ zip xs ys` — Alec, Jul 10 '17 at 17:43

dk14 · Accepted Answer · 2017-07-10T18:52:43.700

1

This is perhaps less efficient than foldRight version, but easier to understand as a start:

//almost same as your List(0,0,0) List(1,1,1)
def combos(n: Int): List[List[Boolean]] = (1 to n).foldLeft(List(List.empty[Boolean])){
  case (acc, _) => acc.map(false :: _) ::: acc.map(true :: _)
}

//apply combo (like 1,1,0) to choose element from either of lists
def applyCombo(a: List[Int], b: List[Int])(combo: List[Boolean]): List[Int] = 
  a zip b zip combo map { case ((x, y), b) => if (b) x else y }

//get all combinations (as boolean) and apply them to a and b
def combine(a: List[Int], b: List[Int]) = combos(a.size) map applyCombo(a, b)

Putting it together, getting rid of intermediate List[List[Boolean]] and adding foldRight:

def combine(aL: List[Int], bL: List[Int]) = (aL zip bL).foldRight(List(List.empty[Int])){
  case ((a, b), acc) => acc.map(a :: _) ::: acc.map(b :: _)
}

Experiment:

a: List[Int] = List(1, 2, 3)
b: List[Int] = List(4, 5, 6)
res73_3: List[List[Int]] = List(
  List(1, 2, 3),
  List(1, 2, 6),
  List(1, 5, 3),
  List(1, 5, 6),
  List(4, 2, 3),
  List(4, 2, 6),
  List(4, 5, 3),
  List(4, 5, 6)
)

Note:

::: isn't much efficient, it could be replaced with acc.flatMap(x => List(a :: x, b :: x)) if you don't care about order of combinations.

edited Jul 10 '17 at 18:52

answered Jul 10 '17 at 18:26

dk14

22,206
4
51
88

Does it make a difference if we use `foldRight` or `foldLeft` in the final `combine` function? couldn't the solution be like this: `def combine2(aL: List[Int], bL: List[Int]) = (aL zip bL).foldLeft(List(List.empty[Int])){ case (acc, (a,b)) => acc.map(a :: _) ::: acc.map(b :: _) }` – Akavall Jul 10 '17 at 19:32
@Akavall `foldLeft` just flips sublists: instead of `List(1,2,3)`, you'd get `List(3,2,1)`, so you would have to reverse it or add new element to the end, which is inefficient for lists. – dk14 Jul 10 '17 at 19:34
But reversing is fairly easy: `def combine2(aL: List[Int], bL: List[Int]) = (aL zip bL).foldLeft(List(List.empty[Int])){ case (acc, (a,b)) => acc.map(_ :+ a) ::: acc.map(_ :+ b) }` – Akavall Jul 10 '17 at 19:39
Is my above suggested solution roughly equivalent to what your `foldRight` solution? – Akavall Jul 10 '17 at 19:41
@Akavall it's equivalent, but much slower: `x :+ a` takes linear time - it traverses the whole `x`, `a :: x` takes constant time - it just links head (a) to a list x. See: http://docs.scala-lang.org/overviews/collections/performance-characteristics.html – dk14 Jul 10 '17 at 20:03
So it is not really equivalent! Thank You very much! – Akavall Jul 10 '17 at 20:54

Make List whose sublists cover all combinations of two input Lists

2 Answers2