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中做到这一点

当前回答

我写了一篇文章来演示如何在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

其他回答

   function perm(xs) {
       return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
        for (var i = 0; i < xs.length; i++) {
          acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
        }
        return acc;
      }, []);
    }

用以下方法进行测试:

console.log(JSON.stringify(perm([1, 2, 3,4])));

2016-03-24 17:07:47

以下非常高效的算法使用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

这是delimited的更简洁的版本

function permutator (inputArr) {
  const result = []

  function permute (arr, m = []) {
    if (arr.length) {
      arr.forEach((item, i) => {
        const restArr = [...arr.slice(0, i), ...arr.slice(i + 1)]
        permute(restArr, [...m, item])
      })
    } else {
      result.push(m)
    }
  }

  permute(inputArr)

  return result
}

2021-08-18 05:33:44

这是一个非常好的map/reduce用例:

function permutations(arr) {
    return (arr.length === 1) ? arr :
    arr.reduce((acc, cv, index) => {
        let remaining = [...arr];
        remaining.splice(index, 1);
        return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
    }, []);
}

首先，我们处理基本情况，如果数组中只有一个项，则返回该数组在所有其他情况下我们创建一个空数组遍历输入数组并添加当前值的数组和剩余数组的所有排列[].concat(cv,a)

2016-12-30 10:54:18

function swap(array1, index1, index2) {
    var temp;
    temp = array1[index1];
    array1[index1] = array1[index2];
    array1[index2] = temp;
}

function permute(a, l, r) {
    var i;
    if (l == r) {
        console.log(a.join(''));
    } else {
        for (i = l; i <= r; i++) {
            swap(a, l, i);
            permute(a, l + 1, r);
            swap(a, l, i);
        }
    }
}


permute(["A","B","C", "D"],0,3);

//示例执行 //更多细节请参考此链接

/ / http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

2016-07-04 21:36:48

JavaScript中的排列?

推荐文章

最新文章

标签