[每日一题]全排列问题的Java实现

数据结构和算法►字符串 , 评论

来源:

经典的全排列问题

描述

给定一个字符串,输出他的全排列。

样例

1
2
3
4
5
6
7
8
9
给定"ABC"

输出:
ABC
ACB
BCA
BAC
CAB
CBA

解题思路:

这道题是数学中的全排列问题,输出结果的个数为n!.

那么怎么获得具体的所有排列呢?

对于ABC来说,

排列的第一位有三种可能:ABC,当第一位确定之后,第二位有两种可能,第三位只有一种可能.

首先确定第一位,可能是3种,分别计算.

1
2
3
4
5
6
7
8
9
A---的第二位可能是B,C,全排列分别为:
  ABC
  ACB
B---的第二位可能是AC,全排列分别为:
  BAC
  BCA
C---的第二位可能是AB,全排列分别为:
  CBA
  CAB

可以看出,ABC的全排列为:

(A+(BC的全排列)) + (B+(AC的全排列)) + (C + (AB的全排列)).

可以使用递归来实现.

实现代码

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
/**
 * 全排列递归实现
 */
private List<String> quanpailie(char[] cs, int current) {
  //结果
  List<String> result = new LinkedList<>();
  //当前指向数组最后一位时,将数组(全排列的一种)输出到结果集里
  if (current == cs.length - 1) {
    result.add(Arrays.toString(cs));
  } else {
    //循环改变数组的第一个位置的值,并求剩下的其他字符的全排列,并装入结果集.
    for (int i = current; i < cs.length; i++) {
      //交换当前字符与下一字符
      swap(cs, current, i);
      //这一块难理解,相当于,在A确定放在第一位的时候,求BC的全排列,并且加上A,形成ABC,ACB放入结果集.
      result.addAll(quanpailie(cs, current + 1));
      //交换回来,方便下一次交换.
      swap(cs, current, i);
    }
  }
  return result;
}

/**
 * 交换数组第b,e位置上的值
 */
private void swap(char[] cs, int b, int e) {
  char tmp = cs[b];
  cs[b] = cs[e];
  cs[e] = tmp;
}

联系我

最后，欢迎关注我的个人公众号【 呼延十 】，会不定期更新很多后端工程师的学习笔记。
也欢迎直接公众号私信或者邮箱联系我，一定知无不言，言无不尽。

完。




ChangeLog

2018-12-11 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。