實現(xiàn)全排列

窮舉法計算二十四的算法的重要一個步驟，是把數(shù)字進行全排列，比如對于一個三個數(shù)的列表 List(1,2,3)，其全排列如下：

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

解決這種問題的一個策略是采用“分而治之”的方法，首先把問題分解成小的問題，比如N個數(shù)的全排列可以分解成 N-1 的全排列再加 1 個數(shù)的排列，然后對每個小的問題給出解決方案。

由此前面可以寫出如下的一個遞歸算法：

def permutations(l:List[Int]):List[List[Int]] = {
    l match {
      case Nil => List(List())
      case (head::tail) =>
        for(p0 <- permutations(tail);i<-0 to (p0 length);(xs,ys)=p0 splitAt i)  yield xs:::List(head):::ys
    }
  }

空列表的全排列為空，N 個數(shù)的全排列為 N-1 個數(shù)的全排列和 1 個數(shù)的全排列，對于每個 N-1 的排列，依次插入剩下的一個數(shù)，就構成了一個新的全排列。 測試如下：

scala> permutations(List(1,2,3)).mkString("\n")
res3: String =
List(1, 2, 3)
List(2, 1, 3)
List(2, 3, 1)
List(1, 3, 2)
List(3, 1, 2)
List(3, 2, 1)

再看看 1,1,2 的情況：

scala> permutations(List(1,1,3)).mkString("\n")
res4: String =
List(1, 1, 3)
List(1, 1, 3)
List(1, 3, 1)
List(1, 3, 1)
List(3, 1, 1)
List(3, 1, 1)

有重復的排列，我們可以直接借助于 List 的 distinct 方法過濾掉重復的值。

scala> permutations(List(1,1,3)).distinct.mkString("\n")
res5: String =
List(1, 1, 3)
List(1, 3, 1)
List(3, 1, 1)

這樣全排列的算法就成了，其實 List 自身已經(jīng)提供了 permutations 方法，不需要自行實現(xiàn):-)

scala> List(1,2,3,4).permutations.mkString("\n")
res6: String =
List(1, 2, 3, 4)
List(1, 2, 4, 3)
List(1, 3, 2, 4)
List(1, 3, 4, 2)
List(1, 4, 2, 3)
List(1, 4, 3, 2)
List(2, 1, 3, 4)
List(2, 1, 4, 3)
List(2, 3, 1, 4)
List(2, 3, 4, 1)
List(2, 4, 1, 3)
List(2, 4, 3, 1)
List(3, 1, 2, 4)
List(3, 1, 4, 2)
List(3, 2, 1, 4)
List(3, 2, 4, 1)
List(3, 4, 1, 2)                                                              
List(3, 4, 2, 1)
List(4, 1, 2, 3)
List(4, 1, 3, 2)
List(4, 2, 1, 3)
List(4, 2, 3, 1)
List(4, 3, 1, 2)
List(4, 3, 2, 1)