1

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

user3799968
  • 1,117
  • 2
  • 8
  • 14
  • What have you tried? There will always be three lists? Or there could be as many of them? – Luis Miguel Mejía Suárez Sep 02 '20 at 12:58
  • 2
    There could be many. I haven't tried any since when I think of something I quickly realise it doesn't work. But I have started to write a function that call it recursively, where the inputs are the first list, and the rest of the list. – user3799968 Sep 02 '20 at 13:01
  • Try to solve the problem by hand, until you can identify an algorithm. Then start to code that. – Luis Miguel Mejía Suárez Sep 02 '20 at 13:03
  • 1
    Possible duplicate of https://stackoverflow.com/questions/8217764/cartesian-product-of-two-lists. The question's asking for only 2 lists, but the top answer at least has a solution that works for multiple lists. There's also [this question](https://stackoverflow.com/questions/14740199/cross-product-in-scala) – user Sep 02 '20 at 18:04

2 Answers2

5

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.

jwvh
  • 50,871
  • 7
  • 38
  • 64
1

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))}
Emiliano Martinez
  • 4,073
  • 2
  • 9
  • 19