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

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


当前回答

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

其他回答

无需外部数组或附加函数即可回答

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permutator(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;
}

我使用了一个字符串而不是一个数组,似乎我的算法消耗的时间更少。我把我的算法贴在这里,我测量的时间正确吗?

console.time('process');

var result = []

function swapper(toSwap){
    let start = toSwap[0]
    let end = toSwap.slice(1)
    return end + start
}


function perm(str){
    let i = str.length
    let filling = i - 1

    let buckets = i*filling
    let tmpSwap = ''
    for(let j=0; j<filling; j++){
        if(j===0){
            result.push(str)
        }else{
          if(j === 1){
              tmpSwap = swapper(str.slice(1))
              result.push(str[0]+ tmpSwap)
              if(j === filling-1 && result.length < buckets){
                  perm(swapper(str))
              }

          }else{
              tmpSwap = swapper(tmpSwap)
              result.push(str[0]+ tmpSwap)
              if(j === filling-1 && result.length < buckets){
                  perm(swapper(str))
              }
          }
        }
    }

    if(result.length = buckets){
      return result
    }else{
      return 'something went wrong'
    }

}





console.log(perm('abcdefghijk'))

console.timeEnd('process');

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

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

大多数其他答案没有利用新的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)}`);

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