JavaScript中的排列?

我试图写一个函数，它做以下工作:

以一个整数数组作为参数(例如[1,2,3,4]) 创建一个包含[1,2,3,4]的所有可能排列的数组，每个排列的长度为4

下面的函数(我在网上找到的)通过接受一个字符串作为参数，并返回该字符串的所有排列来实现这一点

我不知道如何修改它，使它与整数数组一起工作，(我认为这与一些方法在字符串上的工作方式不同于在整数上的工作方式有关，但我不确定…)

let permArr = [];
let usedChars = [];

function permute(input) {
    const chars = input.split("");
    for (let i = 0; i < chars.length; i++) {
        const ch = chars.splice(i, 1);
        usedChars.push(ch);
        if (chars.length === 0) {
            permArr[permArr.length] = usedChars.join("");
        }
        permute(chars.join(""));
        chars.splice(i, 0, ch);
        usedChars.pop();
    }
    return permArr
};

注意:我希望函数返回整数数组，而不是字符串数组。

我真的需要解决方案是在JavaScript。我已经知道如何在python中做到这一点

当前回答

下面是递归函数=> https://recursion.vercel.app/的可视化

 var permute = function (nums) {
  let answer = [];

  var permuter = function (arr, permutation = []) {
    if (arr.length === 0) {
      return answer.push(permutation);
    } else {
      for (let i = 0; i < arr.length; i++) {
        let currentArr = arr.slice();
        let next = currentArr.splice(i, 1);
        permuter(currentArr, permutation.concat(next)); ///we use concat because splice returns an array.
      }
    }
  };

  permuter(nums);

  return answer;
};

2022-11-06 21:38:42

其他回答

我写了一篇文章来演示如何在JavaScript中排列数组。下面是执行此操作的代码。

var count=0;
function permute(pre,cur){ 
    var len=cur.length;
    for(var i=0;i<len;i++){
        var p=clone(pre);
        var c=clone(cur);
        p.push(cur[i]);
        remove(c,cur[i]);
        if(len>1){
            permute(p,c);
        }else{
            print(p);
            count++;
        }
    }
}
function print(arr){
    var len=arr.length;
    for(var i=0;i<len;i++){
        document.write(arr[i]+" ");
    }
    document.write("<br />");
}
function remove(arr,item){
    if(contains(arr,item)){
        var len=arr.length;
        for(var i = len-1; i >= 0; i--){ // STEP 1
            if(arr[i] == item){             // STEP 2
                arr.splice(i,1);              // STEP 3
            }
        }
    }
}
function contains(arr,value){
    for(var i=0;i<arr.length;i++){
        if(arr[i]==value){
            return true;
        }
    }
    return false;
}
function clone(arr){
    var a=new Array();
    var len=arr.length;
    for(var i=0;i<len;i++){
        a.push(arr[i]);
    }
    return a;
}

就叫

permute（[]， [1，2，3，4]）

将工作。关于这是如何工作的详细信息，请参考那篇文章中的解释。

2015-05-27 07:32:08

下面是递归函数=> https://recursion.vercel.app/的可视化

 var permute = function (nums) {
  let answer = [];

  var permuter = function (arr, permutation = []) {
    if (arr.length === 0) {
      return answer.push(permutation);
    } else {
      for (let i = 0; i < arr.length; i++) {
        let currentArr = arr.slice();
        let next = currentArr.splice(i, 1);
        permuter(currentArr, permutation.concat(next)); ///we use concat because splice returns an array.
      }
    }
  };

  permuter(nums);

  return answer;
};

2022-11-06 21:38:42

这是一个非常简洁的递归解决方案，允许您输入输出排列的大小，类似于统计运算符nPr。“排列”。这允许您获得特定大小的所有可能的排列。

function generatePermutations(list, size=list.length) {
    if (size > list.length) return [];
    else if (size == 1) return list.map(d=>[d]); 
    return list.flatMap(d => generatePermutations(list.filter(a => a !== d), size - 1).map(item => [d, ...item]));
}

generatePermutations ([1, 2, 3])

[[1, 2, 3],[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

generatePermutations((1、2、3),2)

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

2020-11-19 02:31:30

对这个问题的大多数回答都使用昂贵的操作，如连续插入和删除数组中的项，或重复复制数组。

相反，这是典型的回溯解决方案:

function permute(arr) {
  var results = [],
      l = arr.length,
      used = Array(l), // Array of bools. Keeps track of used items
      data = Array(l); // Stores items of the current permutation
  (function backtracking(pos) {
    if(pos == l) return results.push(data.slice());
    for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
      used[i] = true;      // Mark item as used
      data[pos] = arr[i];  // Assign item at the current position
      backtracking(pos+1); // Recursive call
      used[i] = false;     // Mark item as not used
    }
  })(0);
  return results;
}

permute([1,2,3,4]); // [  [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1]  ]

由于结果数组将非常大，因此逐个迭代结果而不是同时分配所有数据可能是一个好主意。在ES6中，这可以通过生成器来完成:

function permute(arr) {
  var l = arr.length,
      used = Array(l),
      data = Array(l);
  return function* backtracking(pos) {
    if(pos == l) yield data.slice();
    else for(var i=0; i<l; ++i) if(!used[i]) {
      used[i] = true;
      data[pos] = arr[i];
      yield* backtracking(pos+1);
      used[i] = false;
    }
  }(0);
}

var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}

2015-09-13 16:21:20

以下非常高效的算法使用Heap的方法生成运行时复杂度为O(N!)的N个元素的所有排列:

同样的算法实现为一个空间复杂度为O(N)的生成器:

function* permute(permutation) { var length = permutation.length, c = Array(length).fill(0), i = 1, k, p; yield permutation.slice(); while (i < length) { if (c[i] < i) { k = i % 2 && c[i]; p = permutation[i]; permutation[i] = permutation[k]; permutation[k] = p; ++c[i]; i = 1; yield permutation.slice(); } else { c[i] = 0; ++i; } } } // Memory efficient iteration through permutations: for (var permutation of permute([1, 2, 3])) console.log(permutation); // Simple array conversion: var permutations = [...permute([1, 2, 3])];

性能比较

请随意将您的实现添加到以下benchmark.js测试套件中:

Chrome 48的运行时结果:

99.152ms此算法 153.115 MarkusT女士 401.255 js-combinatorics女士 497.037 Urielzen女士 925.669 Oriol女士 1026.571 SiGanteng女士 2529.841毫秒分隔 3992.622毫秒的猴子 4514.665 Oriol女士

2016-06-02 00:46:05

JavaScript中的排列?

推荐文章

最新文章

标签