Permutações em JavaScript?

138

Estou tentando escrever uma função que faça o seguinte:

  • aceita 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 função abaixo (achei on-line) faz isso usando uma string como argumento e retornando todas as permutações dessa string

Não consegui descobrir como modificá-lo para fazê-lo funcionar com uma matriz de números inteiros (acho que isso tem algo a ver com a maneira como alguns dos métodos funcionam de maneira 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: Estou procurando fazer com que a função retorne matrizes de números 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

pepperdreamteam
fonte

Respostas:

106

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 junção 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])));

Andreas Wong
fonte
@SiGanteng. Algo estranho está acontecendo comigo tentando usar sua função. Eu o mantenho em um arquivo .js, onde tenho toda a minha "função de manipulação de lista". Se eu usá-lo com permute ([1,2,3]), e mais tarde permute ([4,5,6]), a saída da posterior ainda terá o resultado, saída da primeira. Alguma idéia de como consertar isso? Muito Obrigado !
500
3
uma nova pergunta sobre esta resposta .
Anderson Green,
15
Acessando globais em sua função, de forma incorreta!
Shmiddty
123

Um pouco tarde, mas gostaria de adicionar uma versão um pouco mais elegante aqui. Pode ser qualquer matriz ...

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 do ES6 (2015). Também não altera a matriz de entrada original. Funciona no console do 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 ] ]
delimitado
fonte
1
Se você tem uma função fatorial útil (como é bastante provável, considerando que você está lidando com permutações), você pode acelerá-lo, alterando a inicialização escopo externo para var results = new Array(factorial(inputArr.length)), length=0, em seguida, substituir results.push(…)comresults[length++]=…
Cyoce
1
O que a linha var cur, memo = memo || [];faz?
Ricevind
2
@ user2965967 Declara cur e memorando, e inicializa o memorando como o valor do memorando, a menos que seja falsey (incluindo indefinido); nesse caso, será uma matriz vazia. Em outras palavras, é uma maneira menos do que ideal de fornecer ao parâmetro de função um valor padrão.
Sr. Lavalamp
Isso modifica a matriz original.
Shmiddty
2
é a slice()de permute(curr.slice(), m.concat(next))realmente necessário?
Yoav
82

O algoritmo muito eficiente a seguir usa o método Heap para gerar todas as permutações de elementos N 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]));

O mesmo algoritmo implementado como um gerador com complexidade de espaço em O (N):

Comparação de desempenho

Sinta-se à vontade para adicionar sua implementação ao seguinte conjunto de testes benchmark.js :

Resultados em tempo de execução do Chrome 48:

le_m
fonte
1
Como esse código pode ser alterado para fornecer resultados para um n = 2 fixo? Por exemplo, suponha que tenhamos um conjunto de três letras: A, B e C. Podemos perguntar quantas maneiras podemos organizar duas letras desse conjunto. Cada arranjo possível seria um exemplo de permutação. A lista completa de permutações possíveis seria: AB, AC, BA, BC, CA e CB.
A4xrbj1 27/10
1
@ a4xrbj1 Veja, por exemplo, o exemplo de código nesta pergunta: stackoverflow.com/questions/37892738/… - ou você está perguntando especificamente sobre a modificação deste método (da Heap)?
le_m
@le_m sim, especificamente usando este método (de Heap) como é tão rápido
a4xrbj1
@ a4xrbj1 Calcularia todas as combinações de comprimento fixo n (por exemplo, AB, AC, BC para n = 2) usando uma estratégia semelhante ao link fornecido acima (consulte também stackoverflow.com/questions/127704/… ) e, em seguida, para cada combinação calcular todas as suas permutações usando o método de Heap. Casos especiais como n = 2 podem, é claro, ser otimizados.
Le_m 30/10/16
1
A versão do gerador não funciona corretamente, você deve fazê- yield permutation.slice()lo se não cortar, apenas obtém a última permutação calculada.
Beldar
41
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));
macaco
fonte
10
Uau, apesar de sua discrepância e falta de documentos, acho que essa é a resposta mais elegante. Minha explicação sobre esse algoritmo é: Para cada item da matriz (reduzir), selecione todos os outros itens, permuta-os (recursivamente) e concorde com esse item.
Aaron
Tentei esta solução aqui: codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/… Desembrulhei o código de golfe original em um legível, mas é essencialmente o mesmo. O problema é que ele produz duplicatas, e eu tive que fazer um adicional .filter(uniq)no resultado.
Andrei Mikhaylov - lolmaus
1
existe um cisco paralelo ao conceito [1,2,3].length == 3 && "foo" || "bar"ou [1,2].length == 3 && "foo" || "bar"oh meu! Há sim! (or (and (= 3 2) (print "hello!")) (print "goodbye"))
Dmitry
@ lolmaus-AndreyMikhaylov como remover duplicacy Atualize a resposta se você puder
Pardeep Jain
@PardeepJain Dei um link para minha solução acima.
Andrey Mikhaylov - lolmaus
21

Eu melhorei a resposta de SiGanteng .

Agora é possível ligar permutemais de uma vez, porque permArre usedCharssão limpos sempre.

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

Oriol
fonte
10

A função a seguir permite uma matriz de qualquer tipo e chama uma função 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ê chamar 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 ele fará exatamente o que você precisa - preencha uma matriz chamada resultcom 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/

MarkusT
fonte
10

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

Em vez disso, esta é a solução típica de retorno:

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

Como a matriz de resultados será enorme, pode ser uma boa idéia 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<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}
Oriol
fonte
6

Essa é uma tarefa interessante e aqui está minha contribuição. É muito simples e rápido. Se estiver interessado, tenha paciência comigo e continue a ler.

Se você deseja um trabalho rápido, você definitivamente precisa se envolver em programação dinâmica. O que significa que você deve esquecer as abordagens recursivas. Isso é certeza...

Está bem O código do 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 ele 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 buscaremos o resultado final.

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

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

Depois siga estes três passos;

  1. Para cada item do nosso r matriz (resultado), adicionaremos o próximo item da matriz de entrada.
  2. Giraremos cada item com seu comprimento muitas vezes e armazenaremos cada instância na matriz de resultados provisórios t . (bem, exceto o primeiro a não perder tempo com rotação 0)
  3. Quando terminarmos com todos os itens da rmatriz provisória, tdevemos manter o próximo nível de resultados, para que r = t; t = [];continuemos até o comprimento da matriz de entrada.a .

Portanto, a seguir estão nossos passos;

r array   | push next item to |  get length many rotations
          |  each sub array   |       of each subarray
-----------------------------------------------------------
[[1]]     |     [[1,2]]       |     [[1,2],[2,1]]
----------|-------------------|----------------------------
[[1,2],   |     [[1,2,3],     |     [[1,2,3],[2,3,1],[3,1,2],
 [2,1]]   |      [2,1,3]]     |      [2,1,3],[1,3,2],[3,2,1]]
----------|-------------------|----------------------------
previous t|                   |
-----------------------------------------------------------

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

Em vários testes, eu vi resolver 120 permutações de [0,1,2,3,4] por 2000 vezes em 25 ~ 35ms.

Redu
fonte
1
Parece rodar muito rápido, às vezes mais rápido, às vezes mais lento que o método Heap no FF / Ubuntu para diferentes iterações de duração / aquecimento, etc. Precisaria de um jsperf para ver resultados para diferentes mecanismos.
27517 le_m
1
@le_m OK, eu fiz alguns testes @JSBen No Ubuntu e AMD CPU: com o Chrome rotatePerm(o acima) é consistentemente 1,2 mais rápido. Com o FF não há consistência. Após vários testes, às vezes heapPermé 2 vezes mais rápido, algumas vezes, rotatePermé 1,1 vezes mais rápido. Com outros navegadores de kit da web, como Opera ou Epiphany, o sistema é rotatePermconstantemente 1,1 vezes mais rápido. No entanto, o Edge heapPermé consistentemente 1,2 vezes mais rápido a cada vez.
Redu 28/03
1
Agradável! Parece que - pelo menos no FF / Ubuntu - o desempenho do método heap depende principalmente do desempenho da cópia do array. Eu modificado o seu ponto de referência para comparar corte vs. empurrando: jsben.ch/#/x7mYh - em FF e para pequenas matrizes de entrada, empurrando parece muito mais rápido
le_m
2
Seria ótimo se o método heap pudesse ser melhorado em termos de desempenho. A propósito, seu método gera a mesma saída do algoritmo de Langdon (página 16) a partir do mesmo artigo de 1977 que usei como referência para o método de Heap: homepage.math.uiowa.edu/~goodman/22m150.dir/2007/…
le_m 28/03
2
@le_m Acabei de verificar e parece ser a mesma coisa. Eu pareço fazer rotação como ele implementou. Apenas com 40 anos de atraso. Como mencionei na minha resposta, é de fato um método muito simples. Mencionado como a escolha apenas quando a rotação rápida está disponível. Atualmente, estou no Haskell e ele tem um método embutido para fazer uma lista (digamos, matriz) ciclo indefinidamente (avaliação lenta faz uma repetição infinita sem problema) e isso pode ser útil. No entanto, Haskell já tem um padrão permutationsfunção :)
Redu
6

Alguma versão inspirada em Haskell:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]

function perms(xs) {
  if (!xs.length) return [[]];
  return xs.flatMap((xi, i) => {
    // get permutations of xs without its i-th item, then prepend xi to each
    return perms([...xs.slice(0,i), ...xs.slice(i+1)]).map(xsi => [xi, ...xsi]);
  });
}
document.write(JSON.stringify(perms([1,2,3])));

caub
fonte
5

Responda sem a necessidade de uma matriz externa ou função 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;
}
Taylor Hakes
fonte
você pode fazer uma combinação disso? stackoverflow.com/questions/53555563/…
Techdive
5

Atualmente, a versão mais rápida, mais eficiente (resistente) e mais elegante (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`)

Vladislav Ladicky
fonte
Olá, você se importa de explicar o que len % 2 // parity dependent adjacent elements swapsignifica e por que é usado?
Pramesh Bajracharya
Meu código usa o "algoritmo da pilha" para gerar as permutações de matriz. Portanto, se você quiser saber como meu código funciona, leia esta explicação do algoritmo do Heap: en.m.wikipedia.org/wiki/Heap%27s_algorithm
Vladislav Ladicky
Você tentou imprimir o resultado? como controlar o máximo se os elementos da matriz com mais de 10?
Marvix
4

Aqui está uma solução legal

const rotations = ([l, ...ls], right=[]) =>
  l ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []

const permutations = ([x, ...xs]) =>
  x ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
  
console.log(permutations("cat"))

Chris Vouga
fonte
2

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

Resultado:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
debochado
fonte
você pode fazer uma combinação para isso? stackoverflow.com/questions/53555563/…
Techdive
2
   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])));
eb58
fonte
2

A maioria das outras respostas não utiliza as novas funções de gerador de javascript, que são uma solução perfeita para esse tipo de problema. Você provavelmente só precisa de uma permutação de cada vez na memória. Além disso, prefiro gerar uma permutação de um intervalo de índices, pois isso permite que eu indexe cada permutação e pule diretamente para qualquer permutação específica, além de 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)}`);

Doug Coburn
fonte
2
#!/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]));
dashxdr
fonte
2

Aqui está um que eu fiz ...

const permute = (ar) =>
  ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
    {permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);

E aqui está de novo, mas escrito de forma menos concisa! ...

function permute(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
      .map(value=>accumulator.push([].concat(inputArray[index],value)));
    return accumulator;
  },[]);
}

Como funciona: se a matriz tiver mais de um elemento, ela percorre cada elemento e a concatena com uma chamada recursiva para si mesma com os elementos restantes como argumento. Não muda a matriz original.

Roger Heathcote
fonte
2

Resposta funcional usando flatMap:

const getPermutationsFor = (arr, permutation = []) =>
  arr.length === 0
    ? [permutation]
    : arr.flatMap((item, i, arr) =>
        getPermutationsFor(
          arr.filter((_,j) => j !== i),
          [...permutation, item]
        )
      );
jabsatz
fonte
1

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

Saídas permutações lexicograficamente ordenadas. Funciona apenas com números. Em outro caso, você deve alterar o método de troca na linha 34.

tamaz bagdavadze
fonte
1

Semelhante em espírito à solução no estilo Haskell da @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
    }))
  },[])    
}
rplantiko
fonte
1

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 a matriz se houver apenas um item nela
  • Em todos os outros casos
    • criamos uma matriz vazia
    • loop sobre a matriz de entrada
    • e adicione uma matriz do valor atual e todas as permutações da matriz restante [].concat(cv,a)
danielbuechele
fonte
1

Aqui está uma versão mínima do ES6. O achatar e sem funções pode ser retirado do Lodash.

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));

Resultado:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Márton Sári
fonte
1
perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
eb58
fonte
2
Você pode adicionar uma explicação, por favor.
Mehdi Bounya 5/11
3
Embora essa resposta possa resolver a questão, ela não contém explicações de como ou por que o faz.
samlev
1

const permutations = array => {
  let permut = [];
  helperFunction(0, array, permut);
  return permut;
};

const helperFunction = (i, array, permut) => {
  if (i === array.length - 1) {
    permut.push(array.slice());
  } else {
    for (let j = i; j < array.length; j++) {
      swapElements(i, j, array);
      helperFunction(i + 1, array, permut);
      swapElements(i, j, array);
    }
  }
};

function swapElements(a, b, array) {
  let temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

console.log(permutations([1, 2, 3]));

ASHISH RANJAN
fonte
1

Muito tarde. Ainda assim, caso isso ajude alguém.

function permute(arr) {
  if (arr.length == 1) return arr

  let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i + 1)])
                              .map(v => [d,v].join(''))).flat()

  return res
}

console.log(permute([1,2,3,4]))

Nitish Narang
fonte
1

Eu tive uma falha ao criar uma versão disso que tenta ser uma programação concisa, porém legível e puramente funcional.

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

Observe que a formatação do argumento transforma uma sequência de entrada em uma matriz. Não tenho certeza se isso é um pouco mágico demais . Não tenho certeza se eu já vi isso na natureza. Para legibilidade real, eu provavelmente faria input = [...input]a primeira linha da função.

jameslol
fonte
1

Esta é uma implementação do algoritmo do Heap (semelhante ao @ le_m), exceto que é recursiva.

function permute_kingzee(arr,n=arr.length,out=[]) {
    if(n == 1) {
        return out.push(arr.slice());
    } else {
        for(let i=0; i<n; i++) {
            permute_kingzee(arr,n-1, out);
            let j = ( n % 2 == 0 ) ? i : 0;
            let t = arr[n-1];
            arr[n-1] = arr[j];
            arr[j] = t;
        }
        return out;
    }
}

Parece que também é muito mais rápido: https://jsfiddle.net/3brqzaLe/

Zee
fonte
1

Minha primeira contribuição para o site. Além disso, de acordo com os testes que eu fiz, esse código é executado mais rapidamente do que todos os outros métodos mencionados aqui antes desta data; é claro que é mínimo se houver poucos valores, mas o tempo aumenta exponencialmente ao adicionar muitos.

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;
};
Urielzen
fonte
Adicionei uma comparação de desempenho stackoverflow.com/a/37580979/1647737 - sinta-se à vontade para atualizar.
21416 Le_m
0

Eu escrevi um post para demonstrar como permutar uma matriz 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;i<len;i++){
        var p=clone(pre);
        var c=clone(cur);
        p.push(cur[i]);
        remove(c,cur[i]);
        if(len>1){
            permute(p,c);
        }else{
            print(p);
            count++;
        }
    }
}
function print(arr){
    var len=arr.length;
    for(var i=0;i<len;i++){
        document.write(arr[i]+" ");
    }
    document.write("<br />");
}
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<arr.length;i++){
        if(arr[i]==value){
            return true;
        }
    }
    return false;
}
function clone(arr){
    var a=new Array();
    var len=arr.length;
    for(var i=0;i<len;i++){
        a.push(arr[i]);
    }
    return a;
}

Apenas ligue

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

vai funcionar. Para detalhes sobre como isso funciona, consulte a explicação nesse post.

PixelsTech
fonte
0
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);
    }, []);
}
Jonah
fonte