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

以一个整数数组作为参数(例如[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 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])));

其他回答

大多数其他答案没有利用新的javascript生成器函数,这是一个完美的解决这类问题。在内存中,一次可能只需要一个排列。此外,我更喜欢生成一系列索引的排列,因为这允许我对每个排列进行索引,并直接跳转到任何特定的排列,以及用于排列任何其他集合。

// ES6 generator version of python itertools [permutations and combinations] const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; } const isEmpty = arr => arr.length === 0; const permutations = function*(a) { const r = arguments[1] || []; if (isEmpty(a)) yield r; for (let i of range(a.length)) { const aa = [...a]; const rr = [...r, ...aa.splice(i, 1)]; yield* permutations(aa, rr); } } console.log('permutations of ABC'); console.log(JSON.stringify([...permutations([...'ABC'])])); const combinations = function*(a, count) { const r = arguments[2] || []; if (count) { count = count - 1; for (let i of range(a.length - count)) { const aa = a.slice(i); const rr = [...r, ...aa.splice(0, 1)]; yield* combinations(aa, count, rr); } } else { yield r; } } console.log('combinations of 2 of ABC'); console.log(JSON.stringify([...combinations([...'ABC'], 2)])); const permutator = function() { const range = function*(args) { let {begin = 0, count} = args; for (let i = begin; count; count--, i+=1) { yield i; } } const factorial = fact => fact ? fact * factorial(fact - 1) : 1; return { perm: function(n, permutationId) { const indexCount = factorial(n); permutationId = ((permutationId%indexCount)+indexCount)%indexCount; let permutation = [0]; for (const choiceCount of range({begin: 2, count: n-1})) { const choice = permutationId % choiceCount; const lastIndex = permutation.length; permutation.push(choice); permutation = permutation.map((cv, i, orig) => (cv < choice || i == lastIndex) ? cv : cv + 1 ); permutationId = Math.floor(permutationId / choiceCount); } return permutation.reverse(); }, perms: function*(n) { for (let i of range({count: factorial(n)})) { yield this.perm(n, i); } } }; }(); console.log('indexing type permutator'); let i = 0; for (let elem of permutator.perms(3)) { console.log(`${i}: ${elem}`); i+=1; } console.log(); console.log(`3: ${permutator.perm(3,3)}`);

const removeItem = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i+1));
}

const makePermutations = (strArr) => {
  const doPermutation = (strArr, pairArr) => {
    return strArr.reduce((result, permutItem, i) => {
      const currentPair = removeItem(pairArr, i);
      const tempResult = currentPair.map((item) => permutItem+item);
      return tempResult.length === 1 ? result.concat(tempResult) :
             result.concat(doPermutation(tempResult, currentPair));
    }, []);
  }
  return strArr.length === 1 ? strArr :
         doPermutation(strArr, strArr);
}


makePermutations(["a", "b", "c", "d"]);
//result: ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"]

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

有点晚了,但喜欢在这里添加一个稍微优雅的版本。可以是任何数组…

function permutator(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);
}

添加ES6(2015)版本。也不会改变原始输入数组。工作在控制台Chrome…

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

所以…

permutator(['c','a','t']);

收益率…

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

和…

permutator([1,2,3]);

收益率…

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

这是我做的一个…

const permute = (ar) =>
  ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
    {permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);

又来了,只不过写得不那么简洁了……

function permute(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
      .map(value=>accumulator.push([].concat(inputArray[index],value)));
    return accumulator;
  },[]);
}

工作原理:如果数组比一个元素长,它会遍历每个元素,并将其与对自身的递归调用连接起来,其余元素作为参数。它不会改变原始数组。