1. 题目描述

输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

2. 思路分析

把集合看成 2 个部分,第一部分是第一个元素,第二部分是后面剩余元素。所有字符都要与当前集合的第一个元素交换,交换后的元素是固定的,也就是一种情况。

每次交换,都继续处理后面剩余元素,它们又可以分成 2 部分,和之前讲述的一样。就这样一直递归下去,直到最后一个元素,那么就排出了其中一种情况。所有情况放在一起,就是全排列的结果。

3. 代码实现

/**
 * 交换数组指定坐标的2个元素
 * @param {Array} arr
 * @param {Number} i
 * @param {Number} j
 */
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

/**
 * 检测arr[start, end)中, 是否有和arr[end]相等的元素
 * @param {Array} arr
 * @param {Number} start
 * @param {Number} end
 */
function check(arr, start, end) {
  for (let i = start; i < end; ++i) {
    if (arr[end] === arr[i]) {
      return false;
    }
  }
  return true;
}

/**
 * 全排列
 * @param {Array} arr 元素集合
 * @param {Number} n 起始位置
 */
function perm(arr = [], n = 0) {
  const length = arr.length;
  if (length === n) {
    console.log(arr.join(" "));
    return;
  }

  for (let i = n; i < length; ++i) {
    if (check(arr, n, i)) {
      swap(arr, n, i);
      perm(arr, n + 1);
      swap(arr, n, i);
    }
  }
}

/**
 * 测试代码
 */
perm(["a", "b", "c"], 0);
console.log("*".repeat(10));
perm(["a", "b", "b"], 0);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52