CODEWITHSUNDEEP
listscala
Bala
Bala

Reputation: 841

How to permute all combinations involving both lists, with each element preserved at their respective indices?

I'd like to transform a list to another - for example:

val a = List(x,y,z)
val b = List(x1,y1,z1)

Desired output

List(List(x1,y,z),List(x,y1,z),List(x,y,z1),List(x1,y1,z),
     List(x1,y,z1),List(x,y1,z1),List(x1,y1,z1))

The order is to be preserved - hence the built-in combinations function wouldn't be useful. Is there another concise way of doing this with scala?

Upvotes: 4

Views: 323

Answers (3)

0__
0__

Reputation: 67290

So, if the order of the permutations is not relevant but only the fact that all appear, it can be solved. The number of permutations is pow(2, list-length) or 1 << list-length. Here is a version:

def mix[A](a: Seq[A], b: Seq[A]): IndexedSeq[Seq[A]] = {
  val sz = a.size
  require(sz == b.size, "Sequence lengths do not match")
  (0 until 1 << sz).map { i =>
    (a zip b).zipWithIndex.map { case ((ax, bx), j) =>
      if ((i & 1 << j) == 0) ax else bx
    }
  }
}

val a = List("x0", "y0", "z0")
val b = List("x1", "y1", "z1")

mix(a, b)

The outer loop 0 until 1 << sz iterates over all permutations, e.g. here with lists of length 3, it goes from 0 until 7. The inner loop zips the two input lists along with the running index and then flips between the a and b elements depending on the index. This is done using bit-wise comparison with the outer index.

i   1<<j  & == 0
000 001   true  (a)
000 010   true  (a)
000 100   true  (a)

001 001   false (b)
001 010   true  (a)
001 100   true  (a)

010 001   true  (a)
010 010   false (b)
010 100   true  (a)

011 001   false (b)
011 010   false (b)
011 100   true  (a)

etc.

Upvotes: 1

Marth
Marth

Reputation: 24812

def permut[A](l: List[(A,A)]): List[List[A]] = l match {
  case Nil => List(List())   // or Nil :: Nil
  case (a,b) :: tail =>
    val t = permut(tail)
    t.map(a :: _) ::: t.map(b :: _)
}

val a = List("x0", "y0", "z0")
val b = List("x1", "y1", "z1")


scala> permut(a zip b)
res22: List[List[String]] = List(List(x0, y0, z0), List(x0, y0, z1), List(x0, y1, z0), List(x0, y1,
z1), List(x1 , y0, z0), List(x1, y0, z1), List(x1, y1, z0), List(x1, y1, z1))

Upvotes: 3

maasg
maasg

Reputation: 37435

You could use the built-in permutations of Set to calculate and use them as a "belongs to" mask to determine which list should contribute an element to the final combined list. Using this idea, a possible implementation should be something like this:

def xorZip[T](l1:List[T], l2:List[T]):List[List[T]] = {
    def maskedUnzip[T](l:List[((T,T),Int)], mask:Int=>Boolean):List[T] = l.map{ case ((x,y),index) => if (mask(index)) x else y}
    val l1zl2 = l1.zip(l2).zipWithIndex
    val mask = (0 until l1zl2.size).toSet.subsets.toList
    mask.map(mask => maskedUnzip(l1zl2, mask.contains(_)))
  }

Scala REPL: 

scala> val l1 = List("a","b","c")
l1: List[String] = List(a, b, c)

scala> val l2 = List("x","y","z")
l2: List[String] = List(x, y, z)

scala> xorZip(l1,l2)
res0: List[List[String]] = List(List(x, y, z), List(a, y, z), List(x, b, z), List(x, y, c), List(a, b, z), List(a, y, c), List(x, b, c), List(a, b, c))

Upvotes: 0

Related Questions