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

以一个整数数组作为参数(例如[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中做到这一点


当前回答

我改进了SiGanteng的答案。

现在可以多次调用permute,因为permArr和usedChars每次都被清除。

function permute(input) {
    var permArr = [],
        usedChars = [];
    return (function main() {
        for (var i = 0; i < input.length; i++) {
            var ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main();
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr;
    })();
}

函数排列(输入) { var permArr = [], 使用的字符 = []; return (函数 main() { for (var i = 0; i < input.length; i++) { var ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } 主(); input.splice(i, 0, ch); usedChars.pop(); } 返回permArr; })(); } document.write(JSON.stringify(permute([5, 3, 7, 1])));

其他回答

这是一个非常好的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)

一些受到Haskell启发的版本:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]

function perms(xs) { if (!xs.length) return [[]]; return xs.flatMap(x => { // get permutations of xs without x, then prepend x to each return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]); }); // or this duplicate-safe way, suggested by @M.Charbonnier in the comments // return xs.flatMap((x, i) => { // return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]); // }); // or @user3658510's variant // return xs.flatMap((x, i) => { // return perms([...xs.slice(0,i),...xs.slice(i+1)]).map(vs => [x,...vs]); // }); } document.write(JSON.stringify(perms([1,2,3])));

下面的函数排列任意类型的数组,并对发现的每个排列调用指定的回调函数:

/*
  Permutate the elements in the specified array by swapping them
  in-place and calling the specified callback function on the array
  for each permutation.

  Return the number of permutations.

  If array is undefined, null or empty, return 0.

  NOTE: when permutation succeeds, the array should be in the original state
  on exit!
*/
  function permutate(array, callback) {
    // Do the actual permuation work on array[], starting at index
    function p(array, index, callback) {
      // Swap elements i1 and i2 in array a[]
      function swap(a, i1, i2) {
        var t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
      }

      if (index == array.length - 1) {
        callback(array);
        return 1;
      } else {
        var count = p(array, index + 1, callback);
        for (var i = index + 1; i < array.length; i++) {
          swap(array, i, index);
          count += p(array, index + 1, callback);
          swap(array, i, index);
        }
        return count;
      }
    }

    if (!array || array.length == 0) {
      return 0;
    }
    return p(array, 0, callback);
  }

如果你这样称呼它:

  // Empty array to hold results
  var result = [];
  // Permutate [1, 2, 3], pushing every permutation onto result[]
  permutate([1, 2, 3], function (a) {
    // Create a copy of a[] and add that to result[]
    result.push(a.slice(0));
  });
  // Show result[]
  document.write(result);

我认为它将完全满足您的需要-用数组[1,2,3]的排列填充一个名为result的数组。结果是:

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

JSFiddle上的代码稍微清晰一些:http://jsfiddle.net/MgmMg/6/

var inputArray = [1, 2, 3];

var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key)
        .concat(arr.slice(key + 1))
        .reduce(permute, [])
        .map(function (perm) {
            return [item].concat(perm);
        }) || item);
}, []);


alert(JSON.stringify(result));

我对网站的第一个贡献。此外,根据我所做的测试,这段代码比在此之前提到的所有其他方法运行得更快,当然,如果值很少,它是最小的,但是当添加太多时,时间会呈指数增长。

var result = permutations([1,2,3,4]); var output = window.document.getElementById('output'); output.innerHTML = JSON.stringify(result); function permutations(arr) { var finalArr = []; function iterator(arrayTaken, tree) { var temp; for (var i = 0; i < tree; i++) { temp = arrayTaken.slice(); temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]); if (tree >= arr.length) { finalArr.push(temp); } else { iterator(temp, tree + 1); } } } iterator(arr, 1); return finalArr; }; <div id="output"></div>