数组全排列算法递归处理

by

2019-12-24

23:59:41

Leave a comment on 数组全排列算法递归处理

Java

原题是提供一个数组，列出所有数字组成的全排列，排序后，进而随便提供一个index，能够逆向输出第index个排列

比如数组nums={1, 2, 3}，那么全排列排序后结果为：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

因此，完成流程有三个步骤：

1、nums求全排列

2、全排列排序保存起来

3、返回倒数index个数据

这是一种递归，比如上面的{1, 2, 3}，所有的全排列就是【1开头+（2， 3）全排列】+【2开头+（1，3）全排列】+【3开头+（1，2）全排列】，进而继续分拆，最终只有一个数字的时候

先简单画一个图

NewImage

大致流程：

1、遍历nums，将每个数字作为首元素，剩下的部分全排列

2、（1）当首元素是nums[i]=nums[0]=2，nums[0]=2和nums[0]=2交换，这里没变化，去掉nums[0]右移一位递归，继续nums[0]=1和nums[0]=1交换，没变化，去掉nums[0]右移一位递归，继续nums[0]=4和nums[0]=4交换，没变化，去掉nums[0]右移一位递归，此时就剩下一个元素3，nums[left]=nums[right]，这就是递归结束条件，就返回此刻的排列2143，第一行红色排列，虽然这种情况下没变化，但是需要将交换过的数字换回来，因为每一步子数组全排列都是基于相同的父数组来进行遍历

（2）上面第一行红色排列结束后，回到{4,3}分拆的地方，此时就要换首位，也就是4和3交换，即nums[0]=4和nums[i]=3交换，此时由于for循环的缘故i是1，交换后就生成了新的排列2134；这个时候再将nums[0]=4和nums[i]=3换回来，这样分拆前数组还是143

（3）恢复了原样才能继续更外层的循环，1和4交换，原始数组变成了413，进而继续进行上面（1）（2）两步，可以得到2413和2431两个排列

（4）上层恢复了原样，更外层就恢复成了原始的2143，这样才能继续外层交换，2和1交换，最外层数组变成了1243，继续进行上面（1）（2）（3）

写得有点迷糊，说实话debug一把也看得有些晕，说到底还是自身递归能力不强，缺少那种感觉，可以自行研究

上面已经知道了递归的结束条件是最终分裂仅有一个元素的时候，也就是nums[left]==nums[right]，这时候就可以保存整个排列了，可以将数组变成字符串保存在一个List<String>里，最终是要从小到大排序后，输出倒数第index个排列，那么可以将List先排个序然后做一个翻转（这应该不是考察点），获取第index个排列即可

简单Java代码

package com.lihuia.bean;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Copyright (C), 2018-2019
 * FileName: Permutations
 * Author:   lihui
 * Date:     2019/12/25
 */

public class Permutations {
    
    private List<String> list = new ArrayList<>();
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void permuteUnique(int[] nums, int left, int right) {
        if (left == right) {
            list.add(Arrays.toString(nums));
        } else {
            for (int i = left; i <= right; i++) {
                swap(nums, left, i);
                permuteUnique(nums, left + 1, right);
                swap(nums, left, i);
            }
        }
    }
    
    public String getPermute(int[] nums, int index) {
        int length = nums.length;
        permuteUnique(nums, 0, length - 1);
        Collections.sort(list);
        Collections.reverse(list);
        return list.get(index);
    }
}

可以查看下结果：

全排列:    [[2, 1, 4, 3], [2, 1, 3, 4], [2, 4, 1, 3], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [1, 2, 4, 3], [1, 2, 3, 4], [1, 4, 2, 3], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1], [4, 3, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [3, 4, 1, 2], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4]]
从小到大:  [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
从大到小:  [[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 3, 1], [4, 2, 1, 3], [4, 1, 3, 2], [4, 1, 2, 3], [3, 4, 2, 1], [3, 4, 1, 2], [3, 2, 4, 1], [3, 2, 1, 4], [3, 1, 4, 2], [3, 1, 2, 4], [2, 4, 3, 1], [2, 4, 1, 3], [2, 3, 4, 1], [2, 3, 1, 4], [2, 1, 4, 3], [2, 1, 3, 4], [1, 4, 3, 2], [1, 4, 2, 3], [1, 3, 4, 2], [1, 3, 2, 4], [1, 2, 4, 3], [1, 2, 3, 4]]
倒数第四:  [4, 2, 1, 3]

 

到这里其实还没有结束，假如传入的nums里面有重复的元素，因为是存放在ArrayList里，肯定会有重复的排列，最后输出的结果肯定不准，因此可以最后做一下处理，直接lambda表达式stream去重下返回即可

package com.lihuia.bean;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Copyright (C), 2018-2019
 * FileName: Permutations
 * Author:   lihui
 * Date:     2019/12/25
 */

public class Permutations {
    
    private List<String> list = new ArrayList<>();
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void permuteUnique(int[] nums, int left, int right) {
        if (left == right) {
            list.add(Arrays.toString(nums));
        } else {
            for (int i = left; i <= right; i++) {
                swap(nums, left, i);
                permuteUnique(nums, left + 1, right);
                swap(nums, left, i);
            }
        }
    }
    
    public String getPermute(int[] nums, int index) {
        int length = nums.length;
        permuteUnique(nums, 0, length - 1);
        Collections.sort(list);
        Collections.reverse(list);
        return list.stream().distinct().collect(Collectors.toList()).get(index);
    }
}

大部分基本参考google，然后自己体会总结，网上做法很多，但递归方式基本差不多

OVER

发表回复