本文共 5246 字，大约阅读时间需要 17 分钟。

1.最初版本(不是太好理解)

​class FullPerm {    constructor() {        this.result = [];    }    isRepeat(a, start, end) {        for (let i = start; i < end; i++) {            if (a[i] == a[end]) {                return true;            }        }        return false    }    // 计算全排列    allRange(a, k, m) {        if (k == m) {            this.result.push(a.slice(0));        } else {            for (let i = k; i < m; i++) {                if (!this.isRepeat(a, k, i)) {                    let temp = a[k];                    a[k] = a[i];                    a[i] = temp;                    this.allRange(a, k + 1, m);                    temp = a[k];                    a[k] = a[i];                    a[i] = temp;                }            }        }    }}/** * 工具类: *   比如: 传入3,则得到0，1，2的全排列 */class FullPermUtils {    static getNPerm(len) {        let a = [];        for (let i = 0; i < len; i++) {            a.push(i);        }        let perm = new FullPerm();        perm.allRange(a, 0, a.length);        return perm.result;    }}// 测试let ret = FullPermUtils.getNPerm(3);console.log(ret);module.exports = FullPermUtils;/*[ [ 0, 1, 2 ],  [ 0, 2, 1 ],  [ 1, 0, 2 ],  [ 1, 2, 0 ],  [ 2, 1, 0 ],  [ 2, 0, 1 ] ]*/

2.重新实现，支持重复数字的 20201012

package algorithmtest;import java.util.*;public class permutations {    public List
   
    
     > permute(int[] nums) {        List
     
      
       > result = new ArrayList<>();        ArrayList
       
         temp = new ArrayList<>();        boolean[] visit = new boolean[nums.length];        dfs(nums, result, temp, visit);        return result;    }    private void dfs(int[] nums, List
        
         
          > result, ArrayList
          
            temp, boolean[] visit) { if (temp.size() == nums.length) { List
           
             r = (List
            
             ) temp.clone(); // 检查是否这个答案记录过了，避免重复 if (!result.contains(r)) { result.add(r); } return; } for (int i = 0; i < nums.length; i++) { if (visit[i] == false) { int val = nums[i]; temp.add(val); visit[i] = true; dfs(nums, result, temp, visit); visit[i] = false; // 必须保证移除顺序，所以不能用temp.remove((Integer)val); backRemove(temp, val); } } } public void backRemove(ArrayList
             
               arr, int val) { for (int j = arr.size() - 1; j >= 0; j--) { if (arr.get(j) == val) { arr.remove(j); break; } } } public static void main(String[] args) { List
              
               
                > permute = new permutations().permute(new int[]{1, 2, 2, 3}); System.out.println(permute); System.out.println(permute.size()); }}/*[[1, 2, 2, 3], [1, 2, 3, 2], [1, 3, 2, 2], [2, 1, 2, 3], [2, 1, 3, 2], [2, 2, 1, 3], [2, 2, 3, 1], [2, 3, 1, 2], [2, 3, 2, 1], [3, 1, 2, 2], [3, 2, 1, 2], [3, 2, 2, 1]]12 */
               
              
             
            
           
          
         
        
       
      
     
    
   

注意：

1.在从temp中存储接到到result中时，ArrayList要用clone方法存储副本，不然引用会被修改：

List<Integer> r = (List<Integer>) temp.clone();

2.递归前后记得还原现场，因此remove的顺序要保证一致，所以要自己写个方法backRemove从后面移除，不能用remove((Integer)val)这种正向删除。 因为add添加是必然在最后的。

3.ArrayList的remove方法既支持按索引删除，又支持按对象删除，整数类型的，要转化为Integer这样就变为了按对象删除。 自定义类型的，应该要重写equal方法。

3.3个坑，4个人，求全排列

class orderly_think_range_util {    /**     * 求全排列     * @param seatNum 座位数     * @param playerNum 人数     * @returns {[]}     */    static range(seatNum, playerNum) {        let canSelectArr = [];        for (let i = 0; i < playerNum; i++) {            canSelectArr.push(i);        }        let ret = []        orderly_think_range_util.dfs(seatNum, canSelectArr, [], ret);        return ret;    }    static rangeWithEmpty(seatNum, playerNum) {        let canSelectArr = [];        for (let i = 0; i < playerNum; i++) {            canSelectArr.push(i);            canSelectArr.push(-1);        }        let originRet = []        orderly_think_range_util.dfs(seatNum, canSelectArr, [], originRet);        // 去重        let ret = [];        let map = {};        for (let i = 0; i < originRet.length; i++) {            let str = originRet[i].join();            if (map[str] == null) {                map[str] = true;                ret.push(originRet[i]);            }        }        return ret;    }    /**     * 求一个数组是否包含另外一个数组     * @param srcArr 如:[1,2,3]     * @param targetArr 如: [2,3]     * @returns {boolean}     */    static isArrContainArr(srcArr, targetArr) {        let index = srcArr.join().indexOf(targetArr.join());        return index > -1;    }    static dfs(seatNum, canSelectArr, curArr, resultArr) {        if (curArr.length == seatNum) {            resultArr.push(curArr.slice(0));            return        }        for (let i = 0; i < canSelectArr.length; i++) {            let temp = canSelectArr[i];            curArr.push(temp);            canSelectArr.splice(i, 1);            orderly_think_range_util.dfs(seatNum, canSelectArr, curArr, resultArr);            curArr.pop();            canSelectArr.splice(i, 0, temp);        }    }}// // test1// let rangeArr = orderly_think_range_util.range(3, 4);// console.log(rangeArr)//// // test2// let ret = orderly_think_range_util.isArrContainArr([1, 2, 3], [2, 3]);// console.log(ret)//// // test3// let arrRet = orderly_think_range_util.rangeWithEmpty(3, 3)// console.log(arrRet, arrRet.length)module.exports = orderly_think_range_util;

注意：一般splice是删除元素的，其实还可以再指定位置插入元素

let a =[0,1,2,3];console.log("原始:", a)let delIdx = 2;let temp = a[delIdx];a.splice(delIdx, 1);console.log("删除后:", a)a.splice(delIdx, 0, temp);console.log("插入后:", a)原始: [ 0, 1, 2, 3 ]删除后: [ 0, 1, 3 ]插入后: [ 0, 1, 2, 3 ]

转载地址：http://vztli.baihongyu.com/