全排列问题描述为：给定一串数字，生成所有可能的排列。
本文给出两类，一种使用C++通过回溯算法，一种使用Scala通过递归来求解。
首先介绍使用Scala通过递归求解的方法，定义递归关系：对S中的每个x，递归的生成S-x的所有排列的序列，而后将x加到每个序列的前面。这样就能对S里的每个x，产生出了S的所有以x开头的排列。合起来就是所有的排列了。
实现的代码如下：
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]);
}
}
其中，函数参数s表示的是当前序列已经有多少位完成了排列，即前s位完成了排列，当前正在对第s位进行排列。取所有s到size - 1位置的元素作为第s位的数字。回溯的意义是在执行完递归func(vec, s+1);后，需要将之前交换过的元素交换回来，即需要将数组回复原状。
综上，觉得使用Scala的递归思想考虑还是比较简单的，但效率不敢恭维。
