list - 如何置换涉及两个列表的所有组合，每个元素都保留在各自的索引处？

Question

我想将一个列表转换为另一个列表 - 例如：

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

期望的输出

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

订单将被保留 - 因此内置组合功能将无用。scala还有另一种简洁的方法吗？

Answer 1

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

Answer 2

因此，如果排列的顺序不相关，而只是全部出现的事实，则可以解决。排列的数量是pow(2, list-length)或1 << list-length。这是一个版本：

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)

外部循环0 until 1 << sz遍历所有排列，例如这里的列表长度为 3，它从 0 到 7。内部循环将两个输入列表与运行索引一起压缩，然后根据索引在 a 和 b 元素之间翻转。这是通过与外部索引进行逐位比较来完成的。

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.

Answer 3

您可以使用 Set 的内置排列来计算并将它们用作“属于”掩码，以确定哪个列表应将元素贡献给最终组合列表。使用这个想法，一个可能的实现应该是这样的：

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(_)))
  }

斯卡拉 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))