生成全排列算法（Scala和C++实现）

全排列问题描述为：给定一串数字，生成所有可能的排列。
本文给出两类，一种使用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的递归思想考虑还是比较简单的，但效率不敢恭维。