Permutações em JavaScript?

Eu estou tentando escrever uma function que faz o seguinte:

  • recebe uma matriz de números inteiros como argumento (por exemplo, [1,2,3,4])
  • cria uma matriz de todas as permutações possíveis de [1,2,3,4], com cada permutação tendo um comprimento de 4

a function abaixo (eu achei online) faz isso pegando uma string como argumento, e retornando todas as permutações dessa string

Eu não conseguia descobrir como modificá-lo para fazê-lo funcionar com uma matriz de números inteiros, (acho que isso tem algo a ver com como alguns dos methods funcionam de forma diferente em cadeias de caracteres do que em inteiros, mas não tenho certeza. ..)

var permArr = [], usedChars = []; function permute(input) { var i, ch, chars = input.split(""); for (i = 0; i < chars.length; i++) { 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 }; 

Nota: Eu estou olhando para fazer a function retornar matrizes de inteiros , não uma matriz de seqüências de caracteres .

Eu realmente preciso que a solução esteja em JavaScript. Eu já descobri como fazer isso em python

Se você notar, o código realmente divide os caracteres em uma matriz antes de fazer qualquer permutação, então você simplesmente remove a operação de junit e divisão

 var permArr = [], usedChars = []; function permute(input) { var i, ch; for (i = 0; i < input.length; i++) { ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } permute(input); input.splice(i, 0, ch); usedChars.pop(); } return permArr }; document.write(JSON.stringify(permute([5, 3, 7, 1]))); 

Pouco tarde, mas gostaria de adicionar uma versão um pouco mais elegante aqui. Pode ser qualquer array …

 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); } 

Adicionando uma versão ES6 (2015). Também não altera o array de input original. Funciona no console no 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; } 

Assim...

 permutator(['c','a','t']); 

Rendimentos...

 [ [ 'c', 'a', 't' ], [ 'c', 't', 'a' ], [ 'a', 'c', 't' ], [ 'a', 't', 'c' ], [ 't', 'c', 'a' ], [ 't', 'a', 'c' ] ] 

E...

 permutator([1,2,3]); 

Rendimentos...

 [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ] 

O seguinte algoritmo muito eficiente usa o método de Heap para gerar todas as permutações de N elementos com complexidade de tempo de execução em O (N!):

 function permute(permutation) { var length = permutation.length, result = [permutation.slice()], c = new Array(length).fill(0), i = 1, k, p; while (i < length) { if (c[i] < i) { k = i % 2 && c[i]; p = permutation[i]; permutation[i] = permutation[k]; permutation[k] = p; ++c[i]; i = 1; result.push(permutation.slice()); } else { c[i] = 0; ++i; } } return result; } console.log(permute([1, 2, 3])); 
 var inputArray = [1, 2, 3]; var result = inputArray.reduce(function permute(res, item, key, arr) { return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item); }, []); alert(JSON.stringify(result)); 

Eu melhorei a resposta do SiGanteng .

Agora é possível chamar permute mais de uma vez, porque permArr e usedChars são apagados a cada vez.

 function permute(input) { var permArr = [], usedChars = []; return (function main() { for (var i = 0; i < input.length; i++) { var ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } main(); input.splice(i, 0, ch); usedChars.pop(); } return permArr; })(); } 
 function permute(input) { var permArr = [], usedChars = []; return (function main() { for (var i = 0; i < input.length; i++) { var ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } main(); input.splice(i, 0, ch); usedChars.pop(); } return permArr; })(); } document.write(JSON.stringify(permute([5, 3, 7, 1]))); 

A seguinte function permuta uma matriz de qualquer tipo e chama uma function de retorno de chamada especificada em cada permutação encontrada:

 /* 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); } 

Se você ligar assim:

  // 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); 

Eu acho que vai fazer exatamente o que você precisa - preencher uma matriz chamada result com as permutações da matriz [1, 2, 3]. O resultado é:

 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]] 

Código ligeiramente mais claro no JSFiddle: http://jsfiddle.net/MgmMg/6/

Atender sem a necessidade de um array externo ou function adicional

 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; } 

A maioria das respostas a essa pergunta usa operações caras, como inserções contínuas e exclusões de itens em uma matriz, ou copiar arrays de forma reiterativa.

Em vez disso, essa é a solução típica de retrocesso:

 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 
 permute([1,2,3,4]); // [ [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1] ] 

Como a matriz de resultados será enorme, pode ser uma boa ideia iterar os resultados um por um em vez de alocar todos os dados simultaneamente. No ES6, isso pode ser feito com geradores:

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

Alguma versão inspirada em Haskell:

 perms [] = [[]] perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ] 
 function perms(xs){ if (!xs.length) return [[]]; var r=[]; for (var i=0;ix.concat(p))) } return r; } document.write(JSON.stringify(perms([1,2,3]))); 

Aqui está outra solução “mais recursiva”.

 function perms(input) { var data = input.slice(); var permutations = []; var n = data.length; if (n === 0) { return [ [] ]; } else { var first = data.shift(); var words = perms(data); words.forEach(function(word) { for (var i = 0; i < n; ++i) { var tmp = word.slice(); tmp.splice(i, 0, first) permutations.push(tmp); } }); } return permutations; } var str = 'ABC'; var chars = str.split(''); var result = perms(chars).map(function(p) { return p.join(''); }); console.log(result); 
  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; }, []); } 

Teste com:

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

Esta é uma tarefa interessante e aqui está minha contribuição. É muito simples e rápido. Se estiver interessado, por favor, fique comigo e continue a ler.

Se você gostaria deste trabalho rápido, você definitivamente tem que entrar em programação dinâmica. O que significa que você deve esquecer as abordagens recursivas. Isso é certeza…

O código do OK le_m, que usa o método Heap, parece ser o mais rápido até agora. Bem, eu não tenho um nome para o meu algoritmo, não sei se já foi implementado ou não, mas é muito simples e rápido. Como em todas as abordagens de programação dinâmica, começaremos com o problema mais simples e partiremos para o resultado final.

Assumindo que temos uma matriz de a = [1,2,3] começaremos com

 r = [[1]]; // result t = []; // interim result 

Então siga estes três passos;

  1. Para cada item da nossa matriz r (resultado), adicionaremos o próximo item da matriz de input.
  2. Nós giraremos cada item em seu tamanho muitas vezes e armazenaremos cada instância no array de resultado provisório t . (bem exceto pelo primeiro para não perder tempo com 0 rotação)
  3. Uma vez que terminamos com todos os itens do array interino, devemos manter o próximo nível de resultados, então fazemos r = t; t = []; r = t; t = []; e continue até o comprimento da matriz de input a .

Então, os seguintes são os nossos passos;

 r array t array [[1,2]] [[1,2], [2,1]] [[1,2],[2,1]] [[1,2,3],[2,3,1],[3,1,2], [2,1,3],[1,3,2],[3,2,1]] 

Então aqui está o código

 function perm(a){ var r = [[a[0]]], t = [], s = []; if (a.length <= 1) return a; for (var i = 1, la = a.length; i < la; i++){ for (var j = 0, lr = r.length; j < lr; j++){ r[j].push(a[i]); t.push(r[j]); for(var k = 1, lrj = r[j].length; k < lrj; k++){ for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj]; t[t.length] = s; s = []; } } r = t; t = []; } return r; } var arr = [0,1,2,4,5]; console.log("The length of the permutation is:",perm(arr).length); console.time("Permutation test"); for (var z = 0; z < 2000; z++) perm(arr); console.timeEnd("Permutation test"); 
 #!/usr/bin/env node "use strict"; function perm(arr) { if(arr.length<2) return [arr]; var res = []; arr.forEach(function(x, i) { perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) { res.push([x].concat(a)); }); }); return res; } console.log(perm([1,2,3,4])); 

Semelhante em espírito à solução no estilo Haskell por @crl, mas trabalhando com 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 })) },[]) } 

A maioria das outras respostas não utiliza as novas funções do gerador de javascript, que é uma solução perfeita para este tipo de problema. Você provavelmente só precisa de uma permutação no tempo na memory. Além disso, eu prefiro gerar uma permutação de um intervalo de índices, pois isso me permite indexar cada permutação e ir direto para qualquer permutação em particular, bem como ser usado para permutar qualquer outra coleção.

 // 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)}`); 

Este é um caso de uso muito bom para mapear / reduzir:

 function permutations(arr) { return (arr.length === 1) ? arr : arr.reduce((acc, cv, index) => { let remaining = [...arr]; remaining.splice(index, 1); return acc.concat(permutations(remaining).map(a => [].concat(cv,a))); }, []); } 
  • Primeiro, lidamos com o caso base e simplesmente retornamos o array se houver apenas um item nele
  • Em todos os outros casos
    • nós criamos um array vazio
    • loop sobre a matriz de input
    • e adicione uma matriz do valor atual e todas as permutações da matriz restante [].concat(cv,a)

Eu escrevi um post para demonstrar como permutar um array em JavaScript. Aqui está o código que faz isso.

 var count=0; function permute(pre,cur){ var len=cur.length; for(var i=0;i1){ permute(p,c); }else{ print(p); count++; } } } function print(arr){ var len=arr.length; for(var i=0;i"); } function remove(arr,item){ if(contains(arr,item)){ var len=arr.length; for(var i = len-1; i >= 0; i--){ // STEP 1 if(arr[i] == item){ // STEP 2 arr.splice(i,1); // STEP 3 } } } } function contains(arr,value){ for(var i=0;i 

Apenas ligue

permute ([], [1,2,3,4])

vai funcionar. Para detalhes sobre como isso funciona, por favor consulte a explicação na postagem.

 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); }, []); } 
 "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 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; } 
  
  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) } }) } 

Resultado:

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

Minha primeira contribuição para o site. Veja aqui alguns desenhos de explicação do algoritmo por trás do código. Also, according to the tests that I have done, this code runs faster than all the other methods mentioned here before this date, of course it is minimal if there are few values, but the time increases exponentially when adding too many.

 function permutations(arr) { var finalArr = []; function iterator(arrayTaken, tree) { var temp; for (var i = 0; i < tree; i++) { temp = arrayTaken.slice(); temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]); if (tree >= arr.length) { finalArr.push(temp); } else { iterator(temp, tree + 1); } } } iterator(arr, 1); return finalArr; }; 
 const removeItem = (arr, i) => { return arr.slice(0, i).concat(arr.slice(i+1)); } const makePermutations = (strArr) => { const doPermutation = (strArr, pairArr) => { return strArr.reduce((result, permutItem, i) => { const currentPair = removeItem(pairArr, i); const tempResult = currentPair.map((item) => permutItem+item); return tempResult.length === 1 ? result.concat(tempResult) : result.concat(doPermutation(tempResult, currentPair)); }, []); } return strArr.length === 1 ? strArr : doPermutation(strArr, strArr); } makePermutations(["a", "b", "c", "d"]); //result: ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"] /* note: it works like generate permutations with permutation tree permutItem will be a ab abc abcd abd abdc ac acb acbd acd acdb ad adb adbc adc adcb b ba bac bacd bad badc bc bca bcad bcd bcde bd bda bdac bdc bdca ...and so on */ 

Here’s a very short solution, that only works for 1 or 2 long strings. It’s a oneliner, and it’s blazing fast, using ES6 and not depending on jQuery. Apreciar:

 var p = l => l.length<2 ? [l] : l.length==2 ? [l[0]+l[1],l[1]+l[0]] : Function('throw Error("unimplemented")')(); 
 function swap(array1, index1, index2) { var temp; temp = array1[index1]; array1[index1] = array1[index2]; array1[index2] = temp; } function permute(a, l, r) { var i; if (l == r) { console.log(a.join('')); } else { for (i = l; i <= r; i++) { swap(a, l, i); permute(a, l + 1, r); swap(a, l, i); } } } permute(["A","B","C", "D"],0,3); 

// sample execution //for more details refer this link

// http://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/