算法基础之全排列(递归)

全排列(递归)

全排列就是从第一个数字起每个数字分别与他后面的数进行交换。

去重的全排列就是从第一个数起每个数分别与它后面非重复出现的数字交换。

全排列(不去重)

// 搜索
// a 为 需要全排列的数组
// len为需要全排列的数组长度
// index为当前选取到第几位数。(index是从0开始的)
void dfs(int* a, int len, int index){
  if (len <= index) {
  show(a);
  }
  // 枚举排列中第index个位置上的元素  
  // 循环代表的意思：可以把下标为index ~ len-1的数值一一置换到a[index] 中，然后依次求解每个递归问题。
  for (int i = index; i < len; i++) {
    swap(a[index], a[i]);
    dfs(a, len, index+1);
    swap(a[index], a[i]);
  }
}

全排列去重

// 判断是否应该交换。
// 即判断[start,end) 中是否有与a[end]相等的，
// 例子: abccc  避免 c 与 c进行交换，产生重复。
bool isSwap(int* a, int start, int end) {
  for (int i = start; i < end; i++) {
  if (a[i] == a[end]) {
    return false;
  }
  }
  return true;
}
// 搜索
// a 为 需要全排列的数组
// len为需要全排列的数组长度
// index为当前选取到第几位数。(index是从0开始的)
void dfs(int* a, int len, int index){
  // 表明选好了一个排列 (index是从0开始的)，输出
  if (len <= index) {
  show();
  }
  // 枚举排列中第index个位置上的元素  
  // 循环代表的意思：可以把下标为index ~ len-1的数值一一置换到a[index] 中，然后依次求解每个递归问题。
  // 加上isSwap判断是为了避免重复，
  for (int i = index; i < len; i++) {
  if (index == 0 && a[i] == 0) continue;
  if (isSwap(a, index, i)) {
    swap(a[index], a[i]);
    dfs(a, len, index+1);
    swap(a[index], a[i]);

全排列(不去重)的个数

学过排列组合的应该都知道：

n ! n!n!

去重全排列的个数

公式：

n ! ( k 1 ) ! ∗ ( k 2 ) ! ∗ ( k 3 ) ! ∗ . . . ∗ ( k p ) ! \frac{n!}{(k1)! * (k_2)! * (k_3)! * ... * (k_p)!}

(k1)!∗(k

2

)!∗(k

3

)!∗...∗(k

p

)!

n!

n : 串长度(需要全排列的数组长度)

k i k_{i}k

i

：串中第i种元素出现的次数

p:串中不同元素的个数。

例如：数组为{1,1,2,3}

数组长度为4，即n=4，

1的次数是2

2的次数是1

3的次数是1

所以:

4 ! 2 ! ∗ 1 ! ∗ 1 ! \frac{4!}{2!*1!*1!}

2!∗1!∗1!

4!

即12种。