並べ替えを作成するための再帰関数

Question

私は十数回チェックした次の関数を持っていますが、正しく動作するはずですが、結果は間違っています。誰でもこの機能の問題点を指摘できますか？

注：再帰呼び出しで渡されるリストを印刷しています。リストは私が期待する通りです。しかし結果を累積するresultという変数は、最後に正しい順列を含んでいません。また、結果変数へのアクセスを同期しましたが、問題は解決しませんでした。だから、私は同期が問題だとは思わない。コードはそのままコピーして実行できます。

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

出力は次のようになります。Javaのタグがここで何を

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要素の順列との順列間の漸化式を実装していないということで、メイン1と様々な問題があります。 n + 1要素のすべての並べ替えのすべての位置にn要素のすべての順列をとり、n + 1要素のすべての順列を得るために、n要素のすべての順列にn + 1要素を挿入することができるということです。それを行うには

一つの方法は、よりScalatically、次のとおりです。

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 

注意。効率的な解決策は、テール再帰的または反復的な解決策です。私は少し後であなたのために投稿します。