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

Posted1 by 呼延十 on December 11, 2018 Hot:

来源:

经典的全排列问题

描述

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

样例

给定"ABC"

输出:
ABC
ACB
BCA
BAC
CAB
CBA

解题思路:

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

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

对于ABC来说,

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

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

A---的第二位可能是B,C,全排列分别为:
  ABC
  ACB
B---的第二位可能是AC,全排列分别为:
  BAC
  BCA
C---的第二位可能是AB,全排列分别为:
  CBA
  CAB

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

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

可以使用递归来实现.

实现代码

  /**
   * 全排列递归实现
   */
  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

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