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

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


当前回答

无需外部数组或附加函数即可回答

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

其他回答

perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]

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

function permute(permutation) { var length = permutation.length, result = [permutation.slice()], c = new Array(length).fill(0), i = 1, k, p; 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; result.push(permutation.slice()); } else { c[i] = 0; ++i; } } return result; } console.log(permute([1, 2, 3]));

同样的算法实现为一个空间复杂度为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测试套件中:

function permute_SiGanteng(input) { var permArr = [], usedChars = []; function permute(input) { var i, ch; for (i = 0; i < input.length; i++) { ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } permute(input); input.splice(i, 0, ch); usedChars.pop(); } return permArr } return permute(input); } function permute_delimited(inputArr) { var results = []; function permute(arr, memo) { var cur, memo = memo || []; for (var i = 0; i < arr.length; i++) { cur = arr.splice(i, 1); if (arr.length === 0) { results.push(memo.concat(cur)); } permute(arr.slice(), memo.concat(cur)); arr.splice(i, 0, cur[0]); } return results; } return permute(inputArr); } function permute_monkey(inputArray) { return 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); }, []); } function permute_Oriol(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; })(); } function permute_MarkusT(input) { function permutate(array, callback) { function p(array, index, callback) { 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); } var result = []; permutate(input, function(a) { result.push(a.slice(0)); }); return result; } function permute_le_m(permutation) { var length = permutation.length, result = [permutation.slice()], c = new Array(length).fill(0), i = 1, k, p; 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; result.push(permutation.slice()); } else { c[i] = 0; ++i; } } return result; } function permute_Urielzen(arr) { var finalArr = []; var iterator = function (arrayTaken, tree) { for (var i = 0; i < tree; i++) { var 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; } function permute_Taylor_Hakes(arr) { var permutations = []; if (arr.length === 1) { return [ arr ]; } for (var i = 0; i < arr.length; i++) { var subPerms = permute_Taylor_Hakes(arr.slice(0, i).concat(arr.slice(i + 1))); for (var j = 0; j < subPerms.length; j++) { subPerms[j].unshift(arr[i]); permutations.push(subPerms[j]); } } return permutations; } var Combinatorics = (function () { 'use strict'; var version = "0.5.2"; /* combinatory arithmetics */ var P = function(m, n) { var p = 1; while (n--) p *= m--; return p; }; var C = function(m, n) { if (n > m) { return 0; } return P(m, n) / P(n, n); }; var factorial = function(n) { return P(n, n); }; var factoradic = function(n, d) { var f = 1; if (!d) { for (d = 1; f < n; f *= ++d); if (f > n) f /= d--; } else { f = factorial(d); } var result = [0]; for (; d; f /= d--) { result[d] = Math.floor(n / f); n %= f; } return result; }; /* common methods */ var addProperties = function(dst, src) { Object.keys(src).forEach(function(p) { Object.defineProperty(dst, p, { value: src[p], configurable: p == 'next' }); }); }; var hideProperty = function(o, p) { Object.defineProperty(o, p, { writable: true }); }; var toArray = function(f) { var e, result = []; this.init(); while (e = this.next()) result.push(f ? f(e) : e); this.init(); return result; }; var common = { toArray: toArray, map: toArray, forEach: function(f) { var e; this.init(); while (e = this.next()) f(e); this.init(); }, filter: function(f) { var e, result = []; this.init(); while (e = this.next()) if (f(e)) result.push(e); this.init(); return result; }, lazyMap: function(f) { this._lazyMap = f; return this; }, lazyFilter: function(f) { Object.defineProperty(this, 'next', { writable: true }); if (typeof f !== 'function') { this.next = this._next; } else { if (typeof (this._next) !== 'function') { this._next = this.next; } var _next = this._next.bind(this); this.next = (function() { var e; while (e = _next()) { if (f(e)) return e; } return e; }).bind(this); } Object.defineProperty(this, 'next', { writable: false }); return this; } }; /* power set */ var power = function(ary, fun) { var size = 1 << ary.length, sizeOf = function() { return size; }, that = Object.create(ary.slice(), { length: { get: sizeOf } }); hideProperty(that, 'index'); addProperties(that, { valueOf: sizeOf, init: function() { that.index = 0; }, nth: function(n) { if (n >= size) return; var i = 0, result = []; for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]); return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result; }, next: function() { return this.nth(this.index++); } }); addProperties(that, common); that.init(); return (typeof (fun) === 'function') ? that.map(fun) : that; }; /* combination */ var nextIndex = function(n) { var smallest = n & -n, ripple = n + smallest, new_smallest = ripple & -ripple, ones = ((new_smallest / smallest) >> 1) - 1; return ripple | ones; }; var combination = function(ary, nelem, fun) { if (!nelem) nelem = ary.length; if (nelem < 1) throw new RangeError; if (nelem > ary.length) throw new RangeError; var first = (1 << nelem) - 1, size = C(ary.length, nelem), maxIndex = 1 << ary.length, sizeOf = function() { return size; }, that = Object.create(ary.slice(), { length: { get: sizeOf } }); hideProperty(that, 'index'); addProperties(that, { valueOf: sizeOf, init: function() { this.index = first; }, next: function() { if (this.index >= maxIndex) return; var i = 0, n = this.index, result = []; for (; n; n >>>= 1, i++) { if (n & 1) result[result.length] = this[i]; } this.index = nextIndex(this.index); return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result; } }); addProperties(that, common); that.init(); return (typeof (fun) === 'function') ? that.map(fun) : that; }; /* permutation */ var _permutation = function(ary) { var that = ary.slice(), size = factorial(that.length); that.index = 0; that.next = function() { if (this.index >= size) return; var copy = this.slice(), digits = factoradic(this.index, this.length), result = [], i = this.length - 1; for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]); this.index++; return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result; }; return that; }; // which is really a permutation of combination var permutation = function(ary, nelem, fun) { if (!nelem) nelem = ary.length; if (nelem < 1) throw new RangeError; if (nelem > ary.length) throw new RangeError; var size = P(ary.length, nelem), sizeOf = function() { return size; }, that = Object.create(ary.slice(), { length: { get: sizeOf } }); hideProperty(that, 'cmb'); hideProperty(that, 'per'); addProperties(that, { valueOf: function() { return size; }, init: function() { this.cmb = combination(ary, nelem); this.per = _permutation(this.cmb.next()); }, next: function() { var result = this.per.next(); if (!result) { var cmb = this.cmb.next(); if (!cmb) return; this.per = _permutation(cmb); return this.next(); } return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result; } }); addProperties(that, common); that.init(); return (typeof (fun) === 'function') ? that.map(fun) : that; }; /* export */ var Combinatorics = Object.create(null); addProperties(Combinatorics, { C: C, P: P, factorial: factorial, factoradic: factoradic, permutation: permutation, }); return Combinatorics; })(); function permute_Technicalbloke(inputArray) { if (inputArray.length === 1) return inputArray; return inputArray.reduce( function(accumulator,_,index){ permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)]) .map(value=>accumulator.push([inputArray[index],value])); return accumulator; },[]); } var suite = new Benchmark.Suite; var input = [0, 1, 2, 3, 4]; suite.add('permute_SiGanteng', function() { permute_SiGanteng(input); }) .add('permute_delimited', function() { permute_delimited(input); }) .add('permute_monkey', function() { permute_monkey(input); }) .add('permute_Oriol', function() { permute_Oriol(input); }) .add('permute_MarkusT', function() { permute_MarkusT(input); }) .add('permute_le_m', function() { permute_le_m(input); }) .add('permute_Urielzen', function() { permute_Urielzen(input); }) .add('permute_Taylor_Hakes', function() { permute_Taylor_Hakes(input); }) .add('permute_Combinatorics', function() { Combinatorics.permutation(input).toArray(); }) .add('permute_Technicalbloke', function() { permute_Technicalbloke(input); }) .on('cycle', function(event) { console.log(String(event.target)); }) .on('complete', function() { console.log('Fastest is ' + this.filter('fastest').map('name')); }) .run({async: true}); <script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

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女士

一些受到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])));

下面是递归函数=> 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;
};

无需外部数组或附加函数即可回答

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}