全排列問(wèn)題描述為：給定一串?dāng)?shù)字，生成所有可能的排列。
本文給出兩類，一種使用C++通過(guò)回溯算法，一種使用Scala通過(guò)遞歸來(lái)求解。

首先介紹使用Scala通過(guò)遞歸求解的方法，定義遞歸關(guān)系：對(duì)S中的每個(gè)x，遞歸的生成S-x的所有排列的序列，而后將x加到每個(gè)序列的前面。這樣就能對(duì)S里的每個(gè)x，產(chǎn)生出了S的所有以x開(kāi)頭的排列。合起來(lái)就是所有的排列了。
實(shí)現(xiàn)的代碼如下：

def permutation(xs: List[Int]): Set[List[Int]] =
  if (xs == Nil) Set(Nil)
  else {
    for {
      i <- xs.indices
      ys <- func(xs filter (_ != xs(i)))
    }   yield xs(i) :: ys
  }.toSet

func(List(1, 2, 3))

使用回溯法的代碼如下：

void permutation(vector<int> vec, int s) {
    if (s == vec.size()) {
        for_each(vec.begin(), vec.end(), [](int v) { cout << v << " "; });
        cout << endl;
    }

    for (int i = s; i < vec.size(); i++) {
        swap(vec[s], vec[i]);
        func(vec, s+1);
        swap(vec[s], vec[i]);
    }
}

其中，函數(shù)參數(shù)s表示的是當(dāng)前序列已經(jīng)有多少位完成了排列，即前s位完成了排列，當(dāng)前正在對(duì)第s位進(jìn)行排列。取所有s到size - 1位置的元素作為第s位的數(shù)字?；厮莸囊饬x是在執(zhí)行完遞歸func(vec, s+1);后，需要將之前交換過(guò)的元素交換回來(lái)，即需要將數(shù)組回復(fù)原狀。

綜上，覺(jué)得使用Scala的遞歸思想考慮還是比較簡(jiǎn)單的，但效率不敢恭維。