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旋转= ([l，…]Ls]， right=[]) => L !== void 0 ?[[l,…ls,……右),…旋转(ls,[…对，l])]: [] Const排列= ([x，…xs]) => X !== 0 ?排列(x) .flatMap ((p) = >旋转(p (x)…… ])) : [[]] console.log(排列(“猫”)

2019-07-02 07:10:48

其他回答

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

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

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

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

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

2012-07-24 10:34:58

  let permutations = []

  permutate([], {
    color: ['red', 'green'],
    size: ['big', 'small', 'medium'],
    type: ['saison', 'oldtimer']
  })

  function permutate (currentVals, remainingAttrs) {
    remainingAttrs[Object.keys(remainingAttrs)[0]].forEach(attrVal => {
      let currentValsNew = currentVals.slice(0)
      currentValsNew.push(attrVal)

      if (Object.keys(remainingAttrs).length > 1) {
        let remainingAttrsNew = JSON.parse(JSON.stringify(remainingAttrs))
        delete remainingAttrsNew[Object.keys(remainingAttrs)[0]]

        permutate(currentValsNew, remainingAttrsNew)
      } else {
        permutations.push(currentValsNew)
      }
    })
  }

结果:

[ 
  [ 'red', 'big', 'saison' ],
  [ 'red', 'big', 'oldtimer' ],
  [ 'red', 'small', 'saison' ],
  [ 'red', 'small', 'oldtimer' ],
  [ 'red', 'medium', 'saison' ],
  [ 'red', 'medium', 'oldtimer' ],
  [ 'green', 'big', 'saison' ],
  [ 'green', 'big', 'oldtimer' ],
  [ 'green', 'small', 'saison' ],
  [ 'green', 'small', 'oldtimer' ],
  [ 'green', 'medium', 'saison' ],
  [ 'green', 'medium', 'oldtimer' ] 
]

2017-08-17 19:11:03

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

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 =[…]输入]作为函数的第一行。

2019-05-10 06:24:15

这里有另一种“更递归”的解决方案。

输出:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]

2015-01-17 14:37:08

JavaScript中的排列?

推荐文章

最新文章

标签