Scala permutations using two lists

Trickier than I thought! The first step is to calculate the n-times Cartesian product of l2, which can be done using a combination of List.fill, combinations, and permutations (I have a hard time believing that there is no easier way to do this, but I haven't found any):

def prod[T](lst: List[T], n: Int) = List.fill(n)(lst).flatten.combinations(n).flatMap(_.permutations)

The value of n is determined by the size of list l1. In your example prod(l2, 2) will give us List(List(1, 1), List(1, 2), List(2, 1), List(2, 2)). The rest is just an application of map and zip. Together, we have

prod(l2, l1.size).map(l1.zip(_))

Output for l1 = List('a', 'b', 'c'), l2 = List("1", "2"):

List((a,1), (b,1), (c,1))
List((a,1), (b,1), (c,2))
List((a,1), (b,2), (c,1))
List((a,2), (b,1), (c,1))
List((a,1), (b,2), (c,2))
List((a,2), (b,1), (c,2))
List((a,2), (b,2), (c,1))
List((a,2), (b,2), (c,2))

The best way is to use a for comprehension. Much cleaner than the accepted solution IMO :)

for {
  i1 <- List('a', 'b', 'c')
  i2 <- List(1, 2)
} yield List(i1, i2)