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

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


当前回答

这是一个最小的ES6版本。扁平化和无函数可以从Lodash中提取。

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));

结果:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

其他回答

我尝试着做一个简洁而可读的版本,并且是纯函数式编程。

function stringPermutations ([...input]) {
  if (input.length === 1) return input;

  return input
    .map((thisChar, index) => {
      const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
      return stringPermutations(remainingChars)
        .map(remainder => thisChar + remainder);
    })
    .reduce((acc, cur) => [...acc, ...cur]);
}

注意,参数格式化将输入字符串转换为数组。不知道这是不是有点太神奇了。我不确定在野外见过。为了真正的可读性,我可能会用input =[…]输入]作为函数的第一行。

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

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 ] ]

我认为下面的解决方案的唯一不同之处在于,我在出现空情况前一步停止了递归。希望嵌入的评论是充分的解释。

function Permutations (A) // computes all possible ordered sequences of the entries in array A and returns them as an array of arrays
{
var perms = [];

for (var i = 0 ; i < A.length ; i++)
    {
    var rem = A.slice (0); // copy input array to retain remainder of elements after removing i'th element
    var el = rem.splice (i,1);
    if (A.length == 2) {perms.push ([el [0],rem [0]])} // recursion end case
    else 
        {
        var sub = Permutations (rem); // recursive call
        for (var s = 0 ; s < sub.length ; s++) // process recursive response, adding el to the start of each returned sequence
            {
            sub [s].splice (0,0,el [0]);
            perms.push (sub [s]);
            };
        };
    };

return perms ;

};// end of Permutations function

为了解决这个问题,我的想法如下…

1- (n)的总排列是(n!)

2-检查组合小n (n <= 4)。

3-应用递归技术。

if(n == 1) // ['a']
    then permutation is (1) ['a']
if(n == 2) // ['a', 'b']
    then permutations are (2) ['a', 'b'] ['b', 'a']
if(n == 3) // ['a', 'b', 'c']
    then permutations are (6) ['a', 'b', 'c'] ['a', 'c', 'b'] ['b', 'a', 'c'] ['b', 'c', 'a'] ['c', 'a', 'b'] ['c', 'b', 'a']

所以…排列行为是有规律的。

和数组实例的总排列是…所有可能的子排列从原始数组中移除每个单个字符,并将该单个字符与它们相对的子排列连接起来。也许代码能更好地解释这一点。

Bye!

function permutations(array) { let permutationList = []; if(array.length == 1) { return array; } for(let i = 0; i < array.length; i++) { let arrayLength1 = [ array[i] ]; let auxArray = Object.values(array); auxArray.splice(i, 1); let subPermutations = this.permutations(auxArray); for(let j = 0; j < subPermutations.length; j++) { let arrayMerge = arrayLength1.concat(subPermutations[j]); permutationList.push(arrayMerge); } } return permutationList; } let results4 = permutations(['a', 'b' ,'c', 'd']); let results6 = permutations(['a', 'b' ,'c', 'd', 'e', 'f']); console.log(results4.length); console.log(results4); console.log(results6.length); console.log(results6);

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

/*
  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/