在 Scala 中的两个列表之间交换元素时生成所有可能性

Question

寻找一个优雅的解决方案：我有两个列表，希望在交换元素时创建所有可能的结果（具有相同大小的列表，仅在相同位置交换）

val a = List(1,2,3)
val b = List(4,5,6)
...
//result
List(
    (List(1,2,3), List(4,5,6)),
    (List(1,2,6), List(4,5,3)),
    (List(1,5,3), List(4,2,6)),
    (List(1,5,6), List(4,2,3)),
    (List(4,2,3), List(1,5,6)),
    (List(4,2,6), List(1,5,3)),
    (List(4,5,3), List(1,2,6)),
    (List(4,5,6), List(1,2,3))
)

我可以用循环来做，但我想使用不可变列表并且不明白如何用生成器函数来做 (yield)。有什么想法吗？

Answer 1

可能的解决方案是 .subsets 和 .updated 的组合：

scala> Set(0,1,2).subsets
Set()
Set(0)
Set(1)
Set(2)
Set(0, 1)
Set(0, 2)
Set(1, 2)
Set(0, 1, 2)

scala> (a.updated(0,b(0)), b.updated(0,a(0)))
(List(4, 2, 3),List(1, 5, 6))

因此：

scala> (0 to a.length - 1).toSet.subsets
  .map(_.foldLeft((a,b)){ 
    case (acc, i) => (acc._1.updated(i,b(i)), acc._2.updated(i,a(i)))})
(List(1, 2, 3),List(4, 5, 6))
(List(4, 2, 3),List(1, 5, 6))
(List(1, 5, 3),List(4, 2, 6))
(List(1, 2, 6),List(4, 5, 3))
(List(4, 5, 3),List(1, 2, 6))
(List(4, 2, 6),List(1, 5, 3))
(List(1, 5, 6),List(4, 2, 3))
(List(4, 5, 6),List(1, 2, 3))

一旦生成 subsets 个要交换的索引
我们可以 fold 使用 as zero/seed 带有输入列表的元组
在 Set 的每个索引处，我们不变地交换两个列表的元素 a(i)<->b(i)

它很干净，但对于长列表来说效率不高。

Answer 2

这是一种函数式编程友好的方法：

def combine[T](xx: List[T], yy: List[T]): List[(List[T], List[T])] = (xx, yy) match {
  case (Nil, Nil) => Nil
  case (x :: Nil, y :: Nil) => List(
    (List(x), List(y)),
    (List(y), List(x))
  )
  case (x :: xs, y :: ys) =>
    val results = combine(xs, ys)
    results.map { case (rx, ry) => (x :: rx, y :: ry) } ++
      results.map { case (rx, ry) => (y :: rx, x :: ry)}
  case _ =>
    sys.error("Input of non-matching sizes")
}

不幸的是这不是尾递归。

但它有效：

val r = combine(List(1, 2, 3), List(4, 5, 6))
r.foreach(println)

输出：

(List(1, 2, 3),List(4, 5, 6))
(List(1, 2, 6),List(4, 5, 3))
(List(1, 5, 3),List(4, 2, 6))
(List(1, 5, 6),List(4, 2, 3))
(List(4, 2, 3),List(1, 5, 6))
(List(4, 2, 6),List(1, 5, 3))
(List(4, 5, 3),List(1, 2, 6))
(List(4, 5, 6),List(1, 2, 3))

在 Scala 中的两个列表之间交换元素时生成所有可能性

generate all possibilities while swapping elements between two lists in scala

recursion

scala

yield

list

generator