递归函数以创建排列

Question

我有以下函数，我已经检查了十几次，应该完全按照我想要的方式工作，但它最终得到了错误的结果。 谁能指出这个函数有什么问题？

注意：我正在打印出递归调用中传递的列表;并且该列表与我预期的完全一样。 但是，累积结果的称为结果的变量在末尾不包含正确的排列。 此外，我同步了对结果变量的访问，但这并没有解决问题;所以，我不认为同步是一个问题。 代码可以按原样复制和运行。

import collection.mutable._
def permute(list:List[Int], result:StringBuilder):Unit =
{
    val len = list.size
    if (len  == 0) (result.append("|"))
    else
    {   
        for (i <- 0 until len )
        {
            println("========" + list + "===========")
            result.append( list(i) )
            if (i != len -1) 
            {
                //println("Adding comma since i is: " + i)
                result.append(", ")
            }   
            //println("******** Reslut is:" + result + "***********")
            permute( (sublist(list, i) ), result)               
        }   
    }   
    // This function removes just the ith item, and returns the new list.
    def sublist (list:List[Int], i:Int): List[Int] =
    {
        var sub:ListBuffer[Int] = (list.map(x => x)).to[ListBuffer]
        sub.remove(i)
        return sub.toList
    }
}
var res = new StringBuilder("")
permute(List(1,2,3), res)
println(res)

输出为：

========List(1, 2, 3)===========
========List(2, 3)===========
========List(3)===========
========List(2, 3)===========
========List(2)===========
========List(1, 2, 3)===========
========List(1, 3)===========
========List(3)===========
========List(1, 3)===========
========List(1)===========
========List(1, 2, 3)===========
========List(1, 2)===========
========List(2)===========
========List(1, 2)===========
========List(1)===========
**1, 2, 3|32|2, 1, 3|31|31, 2|21|**

Answer 1

我认为 Dici 的解决方案很好，但有点神秘。我认为以下代码更加清晰：

def permutations(list: List[Int]): List[List[Int]] = list match
{
    case Nil | _::Nil => List(list)
    case _ =>(  
        for (i <- list.indices.toList) yield
        {
            val (beforeElem, afterElem) = list.splitAt(i)
            val element = afterElem.head
            val subperm = permutations (beforeElem ++ afterElem.tail)
            subperm.map(element:: _)
        }   
    ).flatten
}
val result = permutations(List (1,2,3,4,5) )
println(result.mkString("n") )

输出将是：

List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)

Answer 2

你的方法存在各种问题，主要是你没有实际实现n元素排列和n + 1元素排列之间的递归关系，也就是说你可以获取n元素的所有排列，并在n元素的每个排列的每个位置插入第 n + 1 个元素，以获得n + 1元素的所有排列。

从规模上讲，一种方法是：

def sortedPermutations(list: List[Int]): List[List[Int]] = list match {
  case Nil | _ :: Nil => List(list)
  case _              => list.indices.flatMap(i => list.splitAt(i) match { 
    case (head, t :: tail) => sortedPermutations(head ::: tail).map(t :: _)
  }).toList
}
println(sortedPermutations(List(1, 2, 3)).map(_.mkString(",")).mkString("|"))

输出：

1,2,3|1,3,2|2,1,3|2,3,1|3,1,2|3,2,1

请注意，由于所有列表串联，这效率非常低。一个有效的解决方案是尾递归或迭代。我稍后会为您发布。