Schön, euch alle zu treffen. Ich heiße Yuji Miyane. Dies ist Qiitas Debüt.
Nun besteht das Problem, alle Kombinationen von Elementen zu untersuchen, um die optimale Lösung zu finden, die im Allgemeinen durch Anwenden eines 100% -Suchalgorithmus zum Erzeugen von Ordnungskombinationen gelöst werden kann.
In mathematischen Begriffen ist "alle Kombinationen von 5 bis 3 in der Reihenfolge" "Permutation" und "Kombination von 5 bis 3 in beliebiger Reihenfolge" "Kombination". Hier werden nur die Ordnungsspalten angezeigt.
Diese Generierungsfunktion ist in den Standardbibliotheken vieler High-End-Sprachen enthalten. In Ruby verfügt die Array-Klasse über eine integrierte Permutationsmethode.
$ irb
> [0, 1, 2].permutation.to_a
=> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
Python hat ein itertool-Modul in seiner Standardbibliothek.
$ python
>>> import itertools
>>> list(itertools.permutations([0, 1, 2]))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
JavaScript jedoch nicht. Wenn Sie nach einer externen Bibliothek suchen, scheint sie irgendwo zu sein, aber ich konnte sie nicht finden, also habe ich sie selbst erstellt (bitte verwenden Sie sie).
(Ergänzung) Ich habe die node.js-Version von itertools von Python gefunden, als ich später gesucht habe, also werde ich sie vorstellen.
Ich zeige Ihnen zuerst den Code und seine Verwendung und erkläre dann, was er tut.
Ich schreibe derzeit alles JavaScript in CoffeeScript und habe zunächst die CoffeeScript-Version erstellt.
https://gist.github.com/higuma/9889266
ArrayPermutation.coffee
# internal: generate permutation recursively
generatePermutation = (perm, pre, post, n) ->
if n > 0
for i in [0...post.length]
rest = post.slice 0
elem = rest.splice i, 1
generatePermutation perm, pre.concat(elem), rest, n - 1
else
perm.push pre
return
###
extend Array.prototype
e.g. [0, 1, 2].permutation(2)
=> [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
###
Array::permutation = (n = @.length) ->
perm = []
generatePermutation perm, [], @, n
perm
Basierend auf dem Ergebnis der Kompilierung des CoffeeScript-Codes wurde der folgende JavaScript-Code mit einigen Änderungen manuell optimiert.
https://gist.github.com/higuma/9889540
ArrayPermutation.js
// JavaScript Array permutation generator
// (optimized from CoffeeScript output: see ArrayPermutation.coffee)
(function() {
var generatePermutation = function(perm, pre, post, n) {
var elem, i, rest, len;
if (n > 0)
for (i = 0, len = post.length; i < len; ++i) {
rest = post.slice(0);
elem = rest.splice(i, 1);
generatePermutation(perm, pre.concat(elem), rest, n - 1);
}
else
perm.push(pre);
};
/*
extend Array.prototype
e.g. [0, 1, 2].permutation(2)
=> [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
*/
Array.prototype.permutation = function(n) {
if (n == null) n = this.length;
var perm = [];
generatePermutation(perm, [], this, n);
return perm;
};
})();
Wenn Sie dies tun (laden), wird dem Array-Objekt eine Permutationsmethode hinzugefügt, sodass es vom Array-Objekt wie folgt aufgerufen werden kann (Sie können es mit demselben Methodennamen und Format wie Ruby aufrufen):
[0, 1, 2].permutation()
// -> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
Wenn Sie nur den Code verwenden möchten, reicht dies aus. Fühlen Sie sich frei, es zu benutzen.
Unten finden Sie eine Beschreibung des Codes. Es ist kurz, aber ich benutze verschiedene Techniken. Erstens sperrt die äußerste anonyme Funktion die darin enthaltene Variable var (hält sie fern) und führt sie nur einmal aus (eine der herkömmlichen Techniken von JavaScript).
(function() {
var generatePermutation = ...
// als lokale Variable verwenden })(); // generatePermutation ist hier undefiniert
Das Herzstück ist die Funktion generatePermutation (die effektiv nur 10 Zeilen, aber ziemlich dicht ist). Beginnen wir mit den folgenden Standardtechniken (Mittelstufe und höher müssen nicht erklärt werden).
post.slice (0) erstellt ein Duplikat des Arrays: Es gibt verschiedene andere Möglichkeiten, concat zu verwenden
post.concat([])[].concat(post)post.concat () ist ebenfalls möglich, funktioniert jedoch möglicherweise nicht mit älteren Browsernrest.splice (i, 1) extrahiert das i-te und verkleinert das Array (Zerstörungsverarbeitung) und gibt das Array der extrahierten Elemente zurück (in diesem Fall 1).pre.concat (elem) erstellt ein neues Array mit danach verkettetem elem (zerstörungsfrei)Eine rekursive Verarbeitung ist erforderlich, um eine Vorwärtskombination zu generieren. Dies ist das wahre Herz, deshalb werde ich es im Detail erklären. Lassen Sie uns das zu verarbeitende Array als "[0, 1, 2, 3]" festlegen und zeigen, wie sich die Argumente (vor, nach) an die erste Ebene geändert haben.
[0, 1, 2, 3]
[0], [1, 2, 3] // Status der Argumente vor, nach (gleich unten) [1], [0, 2, 3] [2], [0, 1, 3] [3], [0, 1, 2]
Dies ist die erste Ebene, ein Element wird der Reihe nach extrahiert, an den Anfang verschoben und die verbleibenden Elemente werden rekursiv verarbeitet. Es wiederholt sich, während die rekursive Ebene (n) um eins dekrementiert wird, und wenn es 0 erreicht, wird es zum Endergebnis (perm) hinzugefügt. Der Ablauf der rekursiven Verarbeitung, wenn der Anfang 0 ist (die maximale rekursive Ebene beträgt 3 und alle 6 Möglichkeiten).
[0, 1, 2, 3]
[0], [1, 2, 3]
[0, 1], [2, 3]
[0, 1, 2], [3] -> [0, 1, 2, 3]
[0, 1, 3], [2] -> [0, 1, 3, 2]
[0, 2], [1, 3]
[0, 2, 1], [3] -> [0, 2, 1, 3]
[0, 2, 3], [2] -> [0, 2, 3, 1]
[0, 3], [1, 2]
[0, 3, 1], [2] -> [0, 3, 1, 2]
[0, 3, 2], [1] -> [0, 3, 2, 1]
[1], [0, 2, 3]
... und so weiter ...
Wichtig hierbei ist, ob die Methode destruktiv ist (sich selbst ändert) oder nicht destruktiv ist (ein neues Array erstellt). Da Splice eine destruktive Methode ist, müssen Sie im Voraus ein Duplikat mit Slice (0) erstellen. ..
Registrieren Sie dies schließlich in der Permutationseigenschaft von Array.prototype und fügen Sie es in das Array-Objekt ein. Dies ist eine bekannte JavaScript-Technik, daher werde ich sie hier nicht erklären.
Array.prototype.permutation = function(n) {
if (n == null) n = this.length;
var perm = [];
generatePermutation(perm, [], this, n);
return perm;
};
Ein letztes Wort. Neulich habe ich eine Webanwendung namens Weather Data Map auf github angekündigt. Die Wetterverteilung wird in Google Maps angezeigt, und Sie können die Trendverteilung an jedem Punkt frei sehen. Versuch es bitte.