CODEWITHSUNDEEP
scala
Akavall
Akavall

Reputation: 86248

Make List whose sublists cover all combinations of two input Lists

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

Upvotes: 1

Views: 575

Answers (2)

dk14
dk14

Reputation: 22374

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.

Upvotes: 1

Alec
Alec

Reputation: 32319

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))

Upvotes: 4

Related Questions