绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
万万没想到,我还是找到了适合我理解的全排列实现方式
2020-06-05 13:54:05

以前刚入行当CRUD boy的时候,我常去刷leetcode,每次遇到排列问题以及它的变种我就抓瞎了,然后搜索别人的实现方式我发现我都无法理解,甚至我还背过这类题的解法,可惜没啥用,过几天又忘记了,想不到时隔多年,我还是找到了一种适合我理解的实现方式。

我们初高中的时候,都学过排列,它的概念是这么说的:从 n 个不同的元素中取出m(1≤m≤n)个不同的元素,按照一定的顺序排成一列,这个过程就叫排列。当 m=n 这种特殊情况出现的时候,就是全排列(All Permutation)。如果选择出的这 m 个元素可以有重复的,这样的排列就是为重复排列(否则就是不重复排列。

如果有这样一道题:求 1,2,3,4,5五个数字的全排列,那么该如何实现呢?我们都知道答案是有120种(5*4*3*2*1=120)。

很明显这这里我们会想到用递归来做,以下是我的心路历程:

permutation.png

我这里只列举了3个数字的,不过也差不多一样的意思。代码应该很容易写出来,递归而已! 先回顾下递归三要素

  1. 一个问题的解可以分解为几个子问题的解

  2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样

  3. 存在递归终止条件
    5个数字都参与了全排列则递归终止

所以代码如下:

public class Permutation {

  public static int count = ;

  /**
   * @param numbers 函数执行前,当前还未参与全排列的数字
   * @param result 函数执行前,已经参与过全排列的数字以及顺序
   */

  public static void allPermutation(ArrayList<Integer> numbers, ArrayList<Integer> result) {

    // 所有数字都参与过了,则排列结束
    if (numbers.isEmpty()) {
      System.out.println(result);
      count++;
      return;
    }

    for (int i = ; i < numbers.size(); i++) {

      // 从剩下的未排列的数字中选择一个加入结果
      ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
      newResult.add(numbers.get(i));

      // 将已选择的数字从未排列的列表中移出
      ArrayList<Integer> newNumbers = (ArrayList<Integer>) numbers.clone();
      newNumbers.remove(i);

      // 递归调用,对于剩余的数字继续生成排列
      allPermutation(newNumbers, newResult);

    }

  }

  public static void main(String[] args) {

    ArrayList<Integer> numbers = new ArrayList<>();
    numbers.add(1);
    numbers.add(2);
    numbers.add(3);
    numbers.add(4);
    numbers.add(5);

    allPermutation(numbers, new ArrayList<>());

    assert count == 120;
  }

}

我认为这里最重要的思想是将数字分为了两堆,分别是未参与排列的数字(numbers)以及已经参与过全排列的数字以及顺序(result)。

万万没想到,CRUD boy也找到了属于自己解题的方式。


分享好友

分享这个小栈给你的朋友们,一起进步吧。

think123
创建时间:2020-06-05 11:55:24
写代码让我学会了思考,而思考又教会了我写代码。 我不保证我写的每个地方都是对的,但是至少可以保证我都是思考过的。 我的努力加上你的,解个bug总没问题吧!
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 小雨滴
    栈主

小栈成员

查看更多
  • ha00012
  • abc
  • sundch
  • zzhq999
戳我,来吐槽~