JavaScript实现穷举排列(permutation)算法谜题解答

谜题

穷举一个数组中各个元素的排列

策略

减而治之、递归

JavaScript解

/**

 * Created by cshao on 12/23/14.

 */

function getPermutation(arr) {

  if (arr.length == 1) {

    return [arr];

  }
  var permutation = [];

  for (var i=0; i<arr.length; i++) {

    var firstEle = arr[i];

    var arrClone = arr.slice(0);

    arrClone.splice(i, 1);

    var childPermutation = getPermutation(arrClone);

    for (var j=0; j<childPermutation.length; j++) {

      childPermutation[j].unshift(firstEle);

    }

    permutation = permutation.concat(childPermutation);

  }

  return permutation;

}
var permutation = getPermutation(['a','b','c']);

console.dir(permutation);

结果

[ [ 'a', 'b', 'c' ],

  [ 'a', 'c', 'b' ],

  [ 'b', 'a', 'c' ],

  [ 'b', 'c', 'a' ],

  [ 'c', 'a', 'b' ],

  [ 'c', 'b', 'a' ] ]