137

Ich versuche eine Funktion zu schreiben, die Folgendes ausführt:

nimmt ein Array von ganzen Zahlen als Argument (z. B. [1,2,3,4])
erstellt ein Array aller möglichen Permutationen von [1,2,3,4], wobei jede Permutation eine Länge von 4 hat

Die folgende Funktion (ich habe sie online gefunden) führt dazu eine Zeichenfolge als Argument aus und gibt alle Permutationen dieser Zeichenfolge zurück

Ich konnte nicht herausfinden, wie ich es ändern kann, damit es mit einem Array von Ganzzahlen funktioniert (ich denke, das hat etwas damit zu tun, wie einige der Methoden bei Zeichenfolgen anders funktionieren als bei Ganzzahlen, aber ich bin mir nicht sicher. ..)

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

Hinweis: Ich möchte, dass die Funktion Arrays von Ganzzahlen zurückgibt , nicht ein Array von Strings .

Ich brauche wirklich die Lösung, um in JavaScript zu sein. Ich habe bereits herausgefunden, wie das in Python geht

javascript permutation Pepperdreamteam
quelle

105

Wenn Sie bemerken, dass der Code die Zeichen tatsächlich in ein Array aufteilt, bevor Sie eine Permutation durchführen, entfernen Sie einfach die Verknüpfungs- und Aufteilungsoperation

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

Erweitern Sie das Snippet

Andreas Wong
quelle

@ SiGanteng. Mir passiert etwas Seltsames, das versucht, Ihre Funktion zu nutzen. Ich behalte es in einer .js, in der ich alle meine "Listenmanipulationsfunktionen" habe. Wenn ich es mit permute ([1,2,3]) und später permute ([4,5,6]) verwende, hat die Ausgabe der späteren immer noch das Ergebnis, die Ausgabe der ersten. Irgendeine Idee, wie man das behebt? Danke vielmals !

500

3

Zu dieser Antwort gibt es eine neue Frage .

Anderson Green

15

Zugriff auf Globals in Ihrer Funktion, schlechte Form!

Shmiddty

123

Etwas spät, möchte aber hier eine etwas elegantere Version hinzufügen. Kann ein beliebiges Array sein ...

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

Hinzufügen einer ES6 (2015) -Version. Mutiert auch nicht das ursprüngliche Eingabearray. Funktioniert in der Konsole in 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;
}

So...

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

Erträge ...

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

Und...

permutator([1,2,3]);

Erträge ...

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

abgegrenzt
quelle

1

Wenn Sie eine Fakultäts - Funktion zur Hand haben (als ziemlich wahrscheinlich ist Erwägen Sie mit Permutationen tun haben ), können Sie es durch Ändern der äußeren Umfang der Initialisierung zu beschleunigen var results = new Array(factorial(inputArr.length)), length=0, dann ersetzen results.push(…)mitresults[length++]=…

Cyoce

1

Was macht line var cur, memo = memo || [];?

Ricevind

2

@ user2965967 Es deklariert cur und memo und initialisiert memo als den Wert von memo, es sei denn, es ist falsch (einschließlich undefiniert). In diesem Fall handelt es sich um ein leeres Array. Mit anderen Worten, es ist eine weniger als ideale Möglichkeit, dem Funktionsparameter einen Standardwert zuzuweisen.

Herr Lavalamp

Dies ändert das ursprüngliche Array.

Shmiddty

2

ist das slice()in permute(curr.slice(), m.concat(next))wirklich notwendig?

Yoav

82

Der folgende sehr effiziente Algorithmus verwendet die Heap-Methode , um alle Permutationen von N Elementen mit Laufzeitkomplexität in O (N!) Zu generieren:

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

Erweitern Sie das Snippet

Der gleiche Algorithmus, der als Generator mit Raumkomplexität in O (N) implementiert ist :

Code-Snippet anzeigen

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

Erweitern Sie das Snippet

Leistungsvergleich

Fühlen Sie sich frei, Ihre Implementierung der folgenden Benchmark.js -Testsuite hinzuzufügen :

Code-Snippet anzeigen

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>

Erweitern Sie das Snippet

Laufzeitergebnisse für Chrome 48:

99,152 ms Dieser Algorithmus
153,115 ms MarkusT
401,255 ms js-Kombinatorik
497,037 ms Urielzen
925,669 ms Oriol
1026,571 ms SiGanteng
2529,841 ms begrenzt
3992,622 ms Affe
4514,665 ms Oriol

le_m
quelle

1

Wie kann dieser Code geändert werden, um Ergebnisse für ein festes n = 2 zu liefern? Angenommen, wir haben drei Buchstaben: A, B und C. Wir könnten fragen, auf wie viele Arten wir zwei Buchstaben aus diesem Satz anordnen können. Jede mögliche Anordnung wäre ein Beispiel für eine Permutation. Die vollständige Liste möglicher Permutationen wäre: AB, AC, BA, BC, CA und CB.

a4xrbj1

1

@ a4xrbj1 Siehe z. B. das Codebeispiel in dieser Frage: stackoverflow.com/questions/37892738/… - oder fragen Sie speziell nach einer Änderung dieser (Heap-) Methode?

le_m

@le_m ja, speziell mit dieser (Heap's) Methode, da es so schnell ist

a4xrbj1

@ a4xrbj1 Ich würde alle Kombinationen fester Länge n (z. B. AB, AC, BC für n = 2) mit einer ähnlichen Strategie wie oben angegeben berechnen (siehe auch stackoverflow.com/questions/127704/… ) und dann für jede Kombination Berechnen Sie alle Permutationen mit der Heap-Methode. Sonderfälle wie n = 2 können natürlich optimiert werden.

le_m

1

Die Generatorversion funktioniert nicht richtig. yield permutation.slice()Wenn Sie nicht schneiden, wird nur die zuletzt berechnete Permutation berechnet.

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

Affe
quelle

10

Wow, trotz seiner Knappheit und des Mangels an Dokumenten denke ich, dass dies die eleganteste Antwort ist. Meine Erklärung für diesen Algorithmus lautet: Wählen Sie für jedes Element im Array (Reduzieren) alle anderen Elemente aus, permutieren Sie sie (rekursiv) und konzentrieren Sie sich auf dieses Element.

Aaron

Ich habe diese Lösung hier ausprobiert : codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/… Ich habe den ursprünglichen Golfcode in einen lesbaren ausgepackt, aber er ist im Wesentlichen der gleiche. Das Problem dabei ist, dass es Duplikate erzeugt, und ich musste .filter(uniq)das Ergebnis zusätzlich bearbeiten.

Andrey Mikhaylov - lolmaus

1

Gibt es ein Lisp parallel zum Konzept [1,2,3].length == 3 && "foo" || "bar"oder [1,2].length == 3 && "foo" || "bar"oh mein Gott! es gibt! (or (and (= 3 2) (print "hello!")) (print "goodbye"))

Dmitry

@ lolmaus-AndreyMikhaylov wie man Duplikate entfernt, bitte aktualisieren Sie die Antwort, wenn Sie können

Pardeep Jain

@PardeepJain Ich habe oben einen Link zu meiner Lösung angegeben.

Andrey Mikhaylov - lolmaus

21

Ich habe verbessert SiGanteng ‚s Antwort .

Jetzt ist es möglich anzurufen permute mehr als einmal , da permArrund usedCharsjedes Mal gelöscht werden.

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

Code-Snippet anzeigen

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

Erweitern Sie das Snippet

Oriol
quelle

10

Die folgende Funktion permutiert ein Array eines beliebigen Typs und ruft bei jeder gefundenen Permutation eine angegebene Rückruffunktion auf:

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

Wenn Sie es so nennen:

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

Ich denke, es wird genau das tun, was Sie brauchen - ein Array resultmit den Permutationen des Arrays [1, 2, 3] füllen . Das Ergebnis ist:

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

Etwas klarerer Code in JSFiddle: http://jsfiddle.net/MgmMg/6/

MarkusT
quelle

10

Die meisten Antworten auf diese Frage verwenden teure Vorgänge wie das kontinuierliche Einfügen und Löschen von Elementen in einem Array oder das wiederholte Kopieren von Arrays.

Stattdessen ist dies die typische Backtracking-Lösung:

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

Da das Ergebnisarray sehr groß sein wird, ist es möglicherweise eine gute Idee, die Ergebnisse einzeln zu wiederholen, anstatt alle Daten gleichzeitig zuzuweisen. In ES6 kann dies mit Generatoren erfolgen:

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
quelle

6

Dies ist eine interessante Aufgabe und hier ist mein Beitrag. Es ist sehr einfach und schnell. Bei Interesse bitte mit mir Kontakt aufnehmen und weiterlesen.

Wenn Sie diesen Job schnell erledigen möchten, müssen Sie sich auf jeden Fall in die dynamische Programmierung einarbeiten. Das heißt, Sie sollten rekursive Ansätze vergessen. Das ist sicher...

OK le_ms Code der die Heap-Methode verwendet, scheint der bisher schnellste zu sein. Nun, ich habe keinen Namen für meinen Algorithmus, ich weiß nicht, ob er bereits implementiert wurde oder nicht, aber er ist sehr einfach und schnell. Wie bei allen dynamischen Programmieransätzen beginnen wir mit dem einfachsten Problem und streben das Endergebnis an.

Angenommen, wir haben eine Reihe von, beginnen a = [1,2,3]wir mit

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

Folgen Sie dann diesen drei Schritten.

Für jedes Element unseres r(Ergebnis-) Arrays fügen wir das nächste Element des Eingabearrays hinzu.
Wir werden jedes Element um seine Länge viele Male drehen und jede Instanz im Zwischenergebnis-Array speichern t. (Nun, bis auf den ersten, der keine Zeit mit 0 Umdrehungen verschwendet.)
Sobald wir mit allen Elementen des rInterim-Arrays fertig sind, tsollte es die nächste Ergebnisebene enthalten, damit wir r = t; t = [];bis zur Länge des Eingabearrays arbeiten und weitermachen können a.

Das Folgende sind also unsere Schritte;

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

Also hier ist der Code

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

Erweitern Sie das Snippet

In mehreren Tests habe ich gesehen, dass die 120 Permutationen von [0,1,2,3,4] 2000 Mal in 25 ~ 35 ms aufgelöst wurden.

Reduzieren
quelle

1

Es scheint sehr schnell zu laufen, manchmal schneller, manchmal langsamer als die Heap-Methode unter FF / Ubuntu für Iterationen mit unterschiedlicher Länge / Aufwärmphase usw. Benötigt ein jsperf, um Ergebnisse für verschiedene Engines zu sehen.

le_m

1

@le_m OK, ich habe einige Tests durchgeführt @JSBen Auf Ubuntu & AMD CPU: Mit Chrome rotatePerm(das obige) ist es durchweg 1.2 schneller. Mit FF gibt es keine Konsistenz. Nach mehreren Tests ist es manchmal heapPerm2-mal schneller , manchmal ist rotatePermes 1,1-mal schneller. Bei anderen Web-Kit-Browsern wie Opera oder Epiphany ist dies rotatePermdurchweg 1,1-mal schneller. Mit Edge heapPermist es jedoch jedes Mal 1,2-mal schneller.

Reduzieren Sie den

1

Nett! Es scheint, dass - zumindest unter FF / Ubuntu - die Leistung der Heap-Methode hauptsächlich von der Leistung des Array-Kopierens abhängt. Ich habe Ihren Benchmark geändert, um Slicing mit Pushing zu vergleichen: jsben.ch/#/x7mYh - auf FF und für kleine Eingabearrays scheint Pushing viel schneller zu sein

le_m

2

Wäre toll, wenn die Heap-Methode leistungsmäßig geschlagen werden könnte. Übrigens generiert Ihre Methode dieselbe Ausgabe wie Langdons Algorithmus (Seite 16) aus demselben Artikel von 1977, den ich als Referenz für Heaps Methode verwendet habe: homepage.math.uiowa.edu/~goodman/22m150.dir/2007/…

le_m

2

@le_m Ich habe gerade überprüft und es scheint das gleiche zu sein. Ich scheine Rotation zu machen, wie er es implementiert hat. Nur mit 40 Jahren Verspätung. Wie ich in meiner Antwort erwähnt habe, ist es in der Tat eine sehr einfache Methode. Erwähnt, nur dann die Wahl zu sein, wenn eine schnelle Rotation verfügbar ist. Momentan bin ich in Haskell und es hat eine eingebaute Methode, um einen Listenzyklus (sagen wir Array) auf unbestimmte Zeit zu erstellen (eine verzögerte Auswertung macht eine unendliche Wiederholung kein Problem) und dies könnte nützlich sein. Dennoch hat Haskell bereits eine Standardfunktion permutations:)

Redu

6

Einige von Haskell inspirierte Versionen:

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

Erweitern Sie das Snippet

caub
quelle

5

Antworten Sie, ohne dass ein externes Array oder eine zusätzliche Funktion erforderlich ist

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
quelle

Kannst du daraus eine Kombination machen? stackoverflow.com/questions/53555563/…

Techdive

5

Die schnellste, effektivste und eleganteste Version (Resorces) heutzutage (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`)

Erweitern Sie das Snippet

Vladislav Ladicky
quelle

Hallo, macht es Ihnen etwas aus zu erklären, was len % 2 // parity dependent adjacent elements swapbedeutet und warum es verwendet wird?

Pramesh Bajracharya

Mein Code verwendet den "Heap-Algorithmus", um die Array-Permutationen zu generieren. Wenn Sie wissen möchten, wie mein Code unter der Haube funktioniert, lesen Sie diese Erklärung des Heap-Algorithmus: en.m.wikipedia.org/wiki/Heap%27s_algorithm

Vladislav Ladicky

Haben Sie versucht, das Ergebnis auszudrucken? Wie steuere ich das Maximum, wenn die Array-Elemente über 10 liegen?

Marvix

4

Hier ist eine coole Lösung

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

Erweitern Sie das Snippet

Chris Vouga
quelle

2

Hier ist eine andere "rekursivere" Lösung.

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

Erweitern Sie das Snippet

Ausgabe:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]

schickling
quelle

Kannst du eine Kombination dafür machen? 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;
      }, []);
    }

Testen Sie es mit:

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

eb58
quelle

2

Die meisten anderen Antworten verwenden nicht die neuen Funktionen des Javascript-Generators, was eine perfekte Lösung für diese Art von Problem darstellt. Sie benötigen wahrscheinlich jeweils nur eine Permutation im Speicher. Außerdem ziehe ich es vor, eine Permutation eines Bereichs von Indizes zu generieren, da dies mir ermöglicht, jede Permutation zu indizieren und direkt zu einer bestimmten Permutation zu springen sowie eine andere Sammlung zu permutieren.

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

Erweitern Sie das Snippet

Doug Coburn
quelle

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
quelle

2

Hier ist eine, die ich gemacht habe ...

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

Und hier ist es wieder aber weniger knapp geschrieben! ...

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

So funktioniert es: Wenn das Array länger als ein Element ist, durchläuft es jedes Element und verkettet es mit einem rekursiven Aufruf an sich selbst mit den verbleibenden Elementen als Argument. Das ursprüngliche Array wird nicht mutiert.

Roger Heathcote
quelle

2

Funktionale Antwort mit flatMap:

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

jabsatz
quelle

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>

Erweitern Sie das Snippet

Gibt lexikographisch geordnete Permutationen aus. Funktioniert nur mit Zahlen. In einem anderen Fall müssen Sie die Swap-Methode in Zeile 34 ändern.

Tamaz Bagdavadze
quelle

1

Ähnlich im Geist wie die Haskell-ähnliche Lösung von @crl, jedoch mit 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
quelle

1

Dies ist ein sehr schöner Anwendungsfall für Map / Reduce:

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

Zuerst behandeln wir den Basisfall und geben das Array einfach zurück, wenn es nur ein Element enthält
In allen anderen Fällen
- Wir erstellen ein leeres Array
- Schleife über das Eingabearray
- und fügen Sie ein Array des aktuellen Werts und aller Permutationen des verbleibenden Arrays hinzu [].concat(cv,a)

danielbuechele
quelle

1

Hier ist eine minimale ES6-Version. Die Abflachung und ohne Funktionen kann aus Lodash gezogen werden.

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

Ergebnis:

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
quelle

1

perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]

eb58
quelle

2

Können Sie bitte eine Erklärung hinzufügen?

Mehdi Bounya

3

Diese Antwort kann zwar die Frage lösen, enthält jedoch keine Erklärung, wie oder warum dies der Fall ist.

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

Erweitern Sie das Snippet

ASHISH RANJAN
quelle

1

Ziemlich spät. Immer noch nur für den Fall, dass dies jemandem hilft.

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

Erweitern Sie das Snippet

Nitish Narang
quelle

1

Ich hatte ein Problem damit, eine Version davon zu erstellen, die versucht, präzise, aber lesbar und rein funktional zu programmieren.

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

Beachten Sie, dass die Argumentformatierung eine Eingabezeichenfolge in ein Array verwandelt. Ich bin mir nicht sicher, ob das ein bisschen zu magisch ist . Ich bin mir nicht sicher, ob ich es in freier Wildbahn gesehen habe. Für eine echte Lesbarkeit würde ich wahrscheinlich stattdessen input = [...input]für die erste Zeile der Funktion tun .

Jameslol
quelle

1

Dies ist eine Implementierung des Heap-Algorithmus (ähnlich dem von @ le_m), außer dass er rekursiv ist.

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

Es sieht so aus, als wäre es auch ziemlich schneller: https://jsfiddle.net/3brqzaLe/

Zee
quelle

1

Mein erster Beitrag zur Seite. Nach den von mir durchgeführten Tests läuft dieser Code schneller als alle anderen hier genannten Methoden vor diesem Datum. Natürlich ist er minimal, wenn nur wenige Werte vorhanden sind, aber die Zeit nimmt exponentiell zu, wenn zu viele hinzugefügt werden.

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
quelle

Ich habe einen Leistungsvergleich hinzugefügt. Stackoverflow.com/a/37580979/1647737 - Sie können ihn jederzeit aktualisieren.

le_m

0

Ich habe einen Beitrag geschrieben , um zu demonstrieren, wie ein Array in JavaScript permutiert wird. Hier ist der Code, der dies tut.

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

Ruf einfach an

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

wird funktionieren. Einzelheiten dazu finden Sie in der Erläuterung in diesem Beitrag.

PixelsTech
quelle

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

Jona
quelle

Permutationen in JavaScript?

Antworten:

Leistungsvergleich

Hier ist eine coole Lösung