JavaScript中的排列?

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

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

当前回答

我想你可能会喜欢这个:

const permute1 = (arr: any[]): any[][] =>
  arr.reduce(
    (acc, curr) =>
      acc.length > 0
        ? acc
            .map((p) =>
              Array.from({ length: p.length + 1 }, (_, i) =>
                p.slice(0, i).concat(curr, p.slice(i))
              )
            )
            .flat()
        : [[curr]],
    []
  );

2022-04-17 15:49:11

其他回答

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

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

2021-12-14 16:11:36

目前最快、最有效、最优雅的版本(2020年)

function getArrayMutations (arr, perms = [], len = arr.length) { if (len === 1) perms.push(arr.slice(0)) for (let i = 0; i < len; i++) { getArrayMutations(arr, perms, len - 1) len % 2 // parity dependent adjacent elements swap ? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]] : [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]] } return perms } const arrayToMutate = [1, 2, 3, 4, 5, 6, 7, 8, 9] const startTime = performance.now() const arrayOfMutations = getArrayMutations(arrayToMutate) const stopTime = performance.now() const duration = (stopTime - startTime) / 1000 console.log(`${arrayOfMutations.length.toLocaleString('en-US')} permutations found in ${duration.toLocaleString('en-US')}s`)

2020-02-09 12:41:12

这是delimited的更简洁的版本

function permutator (inputArr) {
  const result = []

  function permute (arr, m = []) {
    if (arr.length) {
      arr.forEach((item, i) => {
        const restArr = [...arr.slice(0, i), ...arr.slice(i + 1)]
        permute(restArr, [...m, item])
      })
    } else {
      result.push(m)
    }
  }

  permute(inputArr)

  return result
}

2021-08-18 05:33:44

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

2014-07-08 02:24:21

对这个问题的大多数回答都使用昂贵的操作，如连续插入和删除数组中的项，或重复复制数组。

相反，这是典型的回溯解决方案:

function permute(arr) {
  var results = [],
      l = arr.length,
      used = Array(l), // Array of bools. Keeps track of used items
      data = Array(l); // Stores items of the current permutation
  (function backtracking(pos) {
    if(pos == l) return results.push(data.slice());
    for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
      used[i] = true;      // Mark item as used
      data[pos] = arr[i];  // Assign item at the current position
      backtracking(pos+1); // Recursive call
      used[i] = false;     // Mark item as not used
    }
  })(0);
  return results;
}

permute([1,2,3,4]); // [  [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1]  ]

由于结果数组将非常大，因此逐个迭代结果而不是同时分配所有数据可能是一个好主意。在ES6中，这可以通过生成器来完成:

function permute(arr) {
  var l = arr.length,
      used = Array(l),
      data = Array(l);
  return function* backtracking(pos) {
    if(pos == l) yield data.slice();
    else for(var i=0; i<l; ++i) if(!used[i]) {
      used[i] = true;
      data[pos] = arr[i];
      yield* backtracking(pos+1);
      used[i] = false;
    }
  }(0);
}

var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}

2015-09-13 16:21:20

JavaScript中的排列?

推荐文章

最新文章

标签