CODEWITHSUNDEEP
scalafunctional-programmingcartesian-product
user3799968
user3799968

Reputation: 1155

Cartesian product between list inside a list

Input:

[[a,b,c],
[d,e,],
[f,g,h]
]

Desired output:

[
[a,d,f],[a,d,g],[a,d,h],.......[c,e,h]
].

How would you do this in Scala?

Edit: The size of the individual list containing each letter, and the size of the list containing the list, is random. The lists containing letter can have different sizes

Upvotes: 1

Views: 222

Answers (2)

jwvh
jwvh

Reputation: 51271

This is generic for element type but specific for collection type, i.e. List.

def cProd[T](in: List[List[T]]): List[List[T]] =
  in.foldRight(List(List.empty[T])) {
    for {word <- _ ; sentence <- _} yield word :: sentence
  }

It can be made more general for collection type but you'd likely loose some List optimizations.

Upvotes: 5

Emiliano Martinez
Emiliano Martinez

Reputation: 4123

Using Cats with List:

import cats.Semigroupal
import cats.instances.list._

Semigroupal[List]
  .product(Semigroupal[List]
    .product(List("a","b","c"), List("d","e","")),(List("f","g","h")))
  .flatten {case ((a,b), c) => List((a,b,c))}

Upvotes: 1

Related Questions