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

javascript permutation pepperdreamteam
fonte

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

Expandir snippet

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

Há 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]));

Expandir snippet

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

Mostrar snippet de código

function* permute(permutation) {
  var length = permutation.length,
      c = Array(length).fill(0),
      i = 1, k, p;

  yield permutation.slice();
  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;
      yield permutation.slice();
    } else {
      c[i] = 0;
      ++i;
    }
  }
}

// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);

// Simple array conversion:
var permutations = [...permute([1, 2, 3])];

Expandir snippet

Comparação de desempenho

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

Mostrar snippet de código

function permute_SiGanteng(input) {
  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
  }
  return permute(input);
}

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

function permute_monkey(inputArray) {
  return 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);
  }, []);
}

function permute_Oriol(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_MarkusT(input) {
  function permutate(array, callback) {
      function p(array, index, callback) {
          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);
  }
  var result = [];
  permutate(input, function(a) {
      result.push(a.slice(0));
  });
  return result;
}

function permute_le_m(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;
}

function permute_Urielzen(arr) {
    var finalArr = [];
    var iterator = function (arrayTaken, tree) {
        for (var i = 0; i < tree; i++) {
            var 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;
}

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

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

var Combinatorics = (function () {
    'use strict';
    var version = "0.5.2";
    /* combinatory arithmetics */
    var P = function(m, n) {
        var p = 1;
        while (n--) p *= m--;
        return p;
    };
    var C = function(m, n) {
        if (n > m) {
            return 0;
        }
        return P(m, n) / P(n, n);
    };
    var factorial = function(n) {
        return P(n, n);
    };
    var factoradic = function(n, d) {
        var f = 1;
        if (!d) {
            for (d = 1; f < n; f *= ++d);
            if (f > n) f /= d--;
        } else {
            f = factorial(d);
        }
        var result = [0];
        for (; d; f /= d--) {
            result[d] = Math.floor(n / f);
            n %= f;
        }
        return result;
    };
    /* common methods */
    var addProperties = function(dst, src) {
        Object.keys(src).forEach(function(p) {
            Object.defineProperty(dst, p, {
                value: src[p],
                configurable: p == 'next'
            });
        });
    };
    var hideProperty = function(o, p) {
        Object.defineProperty(o, p, {
            writable: true
        });
    };
    var toArray = function(f) {
        var e, result = [];
        this.init();
        while (e = this.next()) result.push(f ? f(e) : e);
        this.init();
        return result;
    };
    var common = {
        toArray: toArray,
        map: toArray,
        forEach: function(f) {
            var e;
            this.init();
            while (e = this.next()) f(e);
            this.init();
        },
        filter: function(f) {
            var e, result = [];
            this.init();
            while (e = this.next()) if (f(e)) result.push(e);
            this.init();
            return result;
        },
        lazyMap: function(f) {
            this._lazyMap = f;
            return this;
        },
        lazyFilter: function(f) {
            Object.defineProperty(this, 'next', {
                writable: true
            });
            if (typeof f !== 'function') {
                this.next = this._next;
            } else {
                if (typeof (this._next) !== 'function') {
                    this._next = this.next;
                }
                var _next = this._next.bind(this);
                this.next = (function() {
                    var e;
                    while (e = _next()) {
                        if (f(e))
                            return e;
                    }
                    return e;
                }).bind(this);
            }
            Object.defineProperty(this, 'next', {
                writable: false
            });
            return this;
        }

    };
    /* power set */
    var power = function(ary, fun) {
        var size = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                that.index = 0;
            },
            nth: function(n) {
                if (n >= size) return;
                var i = 0,
                    result = [];
                for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            },
            next: function() {
                return this.nth(this.index++);
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* combination */
    var nextIndex = function(n) {
        var smallest = n & -n,
            ripple = n + smallest,
            new_smallest = ripple & -ripple,
            ones = ((new_smallest / smallest) >> 1) - 1;
        return ripple | ones;
    };
    var combination = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var first = (1 << nelem) - 1,
            size = C(ary.length, nelem),
            maxIndex = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                this.index = first;
            },
            next: function() {
                if (this.index >= maxIndex) return;
                var i = 0,
                    n = this.index,
                    result = [];
                for (; n; n >>>= 1, i++) {
                    if (n & 1) result[result.length] = this[i];
                }

                this.index = nextIndex(this.index);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* permutation */
    var _permutation = function(ary) {
        var that = ary.slice(),
            size = factorial(that.length);
        that.index = 0;
        that.next = function() {
            if (this.index >= size) return;
            var copy = this.slice(),
                digits = factoradic(this.index, this.length),
                result = [],
                i = this.length - 1;
            for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
            this.index++;
            return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
        };
        return that;
    };
    // which is really a permutation of combination
    var permutation = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var size = P(ary.length, nelem),
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'cmb');
        hideProperty(that, 'per');
        addProperties(that, {
            valueOf: function() {
                return size;
            },
            init: function() {
                this.cmb = combination(ary, nelem);
                this.per = _permutation(this.cmb.next());
            },
            next: function() {
                var result = this.per.next();
                if (!result) {
                    var cmb = this.cmb.next();
                    if (!cmb) return;
                    this.per = _permutation(cmb);
                    return this.next();
                }
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };

    /* export */
    var Combinatorics = Object.create(null);
    addProperties(Combinatorics, {
        C: C,
        P: P,
        factorial: factorial,
        factoradic: factoradic,
        permutation: permutation,
    });
    return Combinatorics;
})();

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

var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];

suite.add('permute_SiGanteng', function() {
    permute_SiGanteng(input);
  })
  .add('permute_delimited', function() {
    permute_delimited(input);
  })
  .add('permute_monkey', function() {
    permute_monkey(input);
  })
  .add('permute_Oriol', function() {
    permute_Oriol(input);
  })
  .add('permute_MarkusT', function() {
    permute_MarkusT(input);
  })
  .add('permute_le_m', function() {
    permute_le_m(input);
  })
  .add('permute_Urielzen', function() {
    permute_Urielzen(input);
  })
  .add('permute_Taylor_Hakes', function() {
    permute_Taylor_Hakes(input);
  })
  .add('permute_Combinatorics', function() {
    Combinatorics.permutation(input).toArray();
  })
  .add('permute_Technicalbloke', function() {
    permute_Technicalbloke(input);
  })
  .on('cycle', function(event) {
    console.log(String(event.target));
  })
  .on('complete', function() {
    console.log('Fastest is ' + this.filter('fastest').map('name'));
  })
  .run({async: true});

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

Expandir snippet

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

99.152ms Este algoritmo
153.115ms MarkusT
401.255ms js-combinatorics
497.037ms Urielzen
925.669ms Oriol
1026.571ms SiGanteng
Delimitado por 2529.841ms
3992.622ms monkey
4514.665ms Oriol

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

Mostrar snippet de código

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

Expandir snippet

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;

Para cada item do nosso r matriz (resultado), adicionaremos o próximo item da matriz de entrada.
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)
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");

Expandir snippet

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

Expandir snippet

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

Expandir snippet

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

Expandir snippet

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

Expandir snippet

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

Expandir snippet

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>

Expandir snippet

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

Expandir snippet

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

Expandir snippet

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

Permutações em JavaScript?

Respostas:

Comparação de desempenho

Aqui está uma solução legal