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中做到这一点

当前回答

"use strict"; function getPermutations(arrP) { var results = []; var arr = arrP; arr.unshift(null); var length = arr.length; while (arr[0] === null) { results.push(arr.slice(1).join('')); let less = null; let lessIndex = null; for (let i = length - 1; i > 0; i--) { if(arr[i - 1] < arr[i]){ less = arr[i - 1]; lessIndex = i - 1; break; } } for (let i = length - 1; i > lessIndex; i--) { if(arr[i] > less){ arr[lessIndex] = arr[i]; arr[i] = less; break; } } for(let i = lessIndex + 1; i<length; i++){ for(let j = i + 1; j < length; j++){ if(arr[i] > arr[j] ){ arr[i] = arr[i] + arr[j]; arr[j] = arr[i] - arr[j]; arr[i] = arr[i] - arr[j]; } } } } return results; } var res = getPermutations([1,2,3,4,5]); var out = document.getElementById('myTxtArr'); res.forEach(function(i){ out.value+=i+', '}); textarea{ height:500px; width:500px; } <textarea id='myTxtArr'></textarea>

输出按字典顺序排列的排列。只对数字有效。在其他情况下，您必须更改第34行上的交换方法。

2016-03-18 20:37:41

其他回答

function nPr(xs, r) {
    if (!r) return [];
    return xs.reduce(function(memo, cur, i) {
        var others  = xs.slice(0,i).concat(xs.slice(i+1)),
            perms   = nPr(others, r-1),
            newElms = !perms.length ? [[cur]] :
                      perms.map(function(perm) { return [cur].concat(perm) });
        return memo.concat(newElms);
    }, []);
}

2015-11-19 17:56:24

  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

在精神上类似于@crl的haskell风格的解决方案，但使用reduce:

function permutations( base ) {
  if (base.length == 0) return [[]]
  return permutations( base.slice(1) ).reduce( function(acc,perm) {
    return acc.concat( base.map( function(e,pos) {
      var new_perm = perm.slice()
      new_perm.splice(pos,0,base[0])
      return new_perm
    }))
  },[])    
}

2016-07-05 12:05:37

   function perm(xs) {
       return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
        for (var i = 0; i < xs.length; i++) {
          acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
        }
        return acc;
      }, []);
    }

用以下方法进行测试:

console.log(JSON.stringify(perm([1, 2, 3,4])));

2016-03-24 17:07:47

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

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

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中的排列?

推荐文章

最新文章

标签