Scala使用Johnson-Trotter算法生成全排列时ArrayBuffer元素未交换问题

问题核心原因 #

• ArrayBuffer是Scala中的可变引用类型，你每次调用result.append(arr)时，存入的是同一个arr对象的内存引用，而非当前状态的副本。后续对arr做的所有交换操作，会同步作用到之前已经存入result的所有元素上，最终所有元素都等于arr遍历结束后的最终状态，也就是回到了初始的(1,2,3)，所以会看到6次重复输出。
• 你当前的Johnson-Trotter算法实现逻辑本身存在缺陷，没有正确实现「移动最大可移动元素」「翻转更大元素方向」的核心逻辑，就算修复了引用问题，也没法输出正确的全排列。

修复方案 #

1. 修复引用问题 #

把所有result.append(arr)的地方替换为result.append(arr.clone())，每次存入当前arr的独立副本，避免后续修改影响已存结果。

2. 修正Johnson-Trotter算法实现 #

完整修正后的可运行代码如下：

import scala.collection.mutable.ArrayBuffer

object Code {
  // 定义元素类，存储值和移动方向（true为向左，false为向右）
  case class Element(value: Int, var left: Boolean = true)

  // 判断指定位置元素是否可移动
  def canMove(arr: Array[Element], index: Int): Boolean = {
    val e = arr(index)
    if (e.left) index > 0 && arr(index - 1).value < e.value
    else index < arr.length - 1 && arr(index + 1).value < e.value
  }

  // 移动指定位置的元素
  def move(arr: Array[Element], index: Int): Unit = {
    val e = arr(index)
    if (e.left) {
      val temp = arr(index - 1)
      arr(index - 1) = arr(index)
      arr(index) = temp
    } else {
      val temp = arr(index + 1)
      arr(index + 1) = arr(index)
      arr(index) = temp
    }
  }

  // 翻转所有大于指定值的元素的移动方向
  def reverseLarger(arr: Array[Element], value: Int): Unit = {
    arr.foreach(e => if (e.value > value) e.left = !e.left)
  }

  // 找到当前最大的可移动元素的下标
  def findMaxMovable(arr: Array[Element]): Int = {
    var maxVal = -1
    var maxIdx = -1
    arr.indices.foreach { i =>
      if (canMove(arr, i) && arr(i).value > maxVal) {
        maxVal = arr(i).value
        maxIdx = i
      }
    }
    maxIdx
  }

  def permutation(n: Int): ArrayBuffer[List[Int]] = {
    val result = new ArrayBuffer[List[Int]]()
    // 初始化元素，初始方向都向左
    val arr = (1 to n).map(Element(_)).toArray
    // 存入第一个排列
    result.append(arr.map(_.value).toList)

    var maxMovableIdx = findMaxMovable(arr)
    while (maxMovableIdx != -1) {
      val maxVal = arr(maxMovableIdx).value
      // 移动最大可移动元素
      move(arr, maxMovableIdx)
      // 翻转所有更大元素的方向
      reverseLarger(arr, maxVal)
      // 存入当前生成的新排列
      result.append(arr.map(_.value).toList)
      // 查找下一个最大可移动元素
      maxMovableIdx = findMaxMovable(arr)
    }
    result
  }

  def main(args: Array[String]): Unit = {
    val perm = permutation(3)
    perm.foreach(p => println(p.mkString(" ")))
  }
}

运行输出 #

1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3

完全符合3个元素的全排列要求，也符合Johnson-Trotter算法相邻交换生成排列的顺序特性。

内容的提问来源于stack exchange，提问作者Devvrat Chaubal