Agréable de vous rencontrer tous. Je m'appelle Yuji Miyane. Ce sont les débuts de Qiita.
Maintenant, il y a le problème de l'inspection de toutes les combinaisons d'éléments pour trouver la solution optimale, qui peut généralement être résolue en appliquant un algorithme de recherche à 100% pour générer des combinaisons ordinales.
En termes mathématiques, «toutes les combinaisons dans lesquelles 5 à 3 sont rangées dans l'ordre» est «permutation», et «combinaison dans laquelle 3 sont sélectionnées parmi 5 dans n'importe quel ordre» est «combinaison». Seules les colonnes ordinales sont affichées ici.
Cette fonctionnalité de génération est incluse dans les bibliothèques standard de nombreux langages haut de gamme. Dans Ruby, la classe Array a une méthode de permutation intégrée.
$ 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 a un module itertool dans sa bibliothèque standard.
$ 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)]
Mais pas JavaScript. Si vous recherchez une bibliothèque externe, elle semble être quelque part, mais je ne l'ai pas trouvée, alors je l'ai créée moi-même (veuillez l'utiliser).
(Supplément) J'ai trouvé la version node.js d'itertools de Python lorsque j'ai cherché plus tard, donc je vais la présenter.
Je vais vous montrer le code et comment l'utiliser d'abord, puis vous expliquer ce qu'il fait.
J'écris actuellement tout JavaScript dans CoffeeScript, et j'ai initialement créé la version CoffeeScript.
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
Basé sur le résultat de la compilation du code CoffeeScript, le code JavaScript suivant a été optimisé manuellement avec une petite modification.
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;
};
})();
Faire (charger) cela ajoute une méthode de permutation à l'objet Array afin qu'il puisse être appelé à partir de l'objet Array comme suit (vous pouvez l'appeler avec le même nom de méthode et le même format que ruby):
[0, 1, 2].permutation()
// -> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
Si vous souhaitez simplement utiliser le code, cela suffit. Sentez-vous libre de l'utiliser.
Vous trouverez ci-dessous une description du code. C'est court, mais j'utilise différentes techniques. Tout d'abord, la fonction anonyme la plus externe verrouille la variable var à l'intérieur (en la gardant à l'écart) et ne l'exécute qu'une seule fois (une des techniques conventionnelles de JavaScript).
(function() {
var generatePermutation = ...
// utiliser comme variable locale })(); // generatePermutation n'est pas défini ici
Au cœur se trouve la fonction generatePermutation (qui ne fait effectivement que 10 lignes mais assez dense). Commençons par les techniques standard suivantes (intermédiaires et supérieurs n'auront pas besoin d'expliquer).
post.slice (0) fait un double du tableau: il existe plusieurs autres façons d'utiliser concat
post.concat([])[].concat(post)post.concat () est également possible, mais peut ne pas fonctionner avec les anciens navigateursrest.splice (i, 1) extrait le i-ème et réduit le tableau (traitement de destruction), et retourne le tableau des éléments extraits (1 dans ce cas).pre.concat (elem) crée un nouveau tableau avec elem concaténé après lui (non destructif)Un traitement récursif est nécessaire pour générer une combinaison directe. C'est le vrai cœur, je vais donc l'expliquer en détail. Définissons le tableau à traiter comme [0, 1, 2, 3], et montrons comment les arguments (pré, post) passés au premier niveau changent.
[0, 1, 2, 3]
[0], [1, 2, 3] // État des arguments avant, après (idem ci-dessous) [1], [0, 2, 3] [2], [0, 1, 3] [3], [0, 1, 2]
Il s'agit du premier niveau, un élément est extrait dans l'ordre, déplacé au début et les éléments restants sont traités de manière récursive. Il se reproduit en décrémentant le niveau récursif (n) de un, et lorsqu'il atteint 0, il est ajouté au résultat final (perm). Affiche le flux du traitement récursif lorsque le début est à 0 (le niveau récursif maximum est de 3 et il y a 6 façons au total).
[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]
... etc ...
L'important ici est de savoir si la méthode est destructive (se modifie elle-même) ou non (crée un nouveau tableau), et comme l'épissure est une méthode destructive, vous devez faire une duplication avec slice (0) à l'avance. ..
Enfin, enregistrez-le dans la propriété permutation de Array.prototype et incluez-le dans l'objet Array. C'est une technique JavaScript bien connue, donc je ne l'expliquerai pas ici.
Array.prototype.permutation = function(n) {
if (n == null) n = this.length;
var perm = [];
generatePermutation(perm, [], this, n);
return perm;
};
Un dernier mot. L'autre jour, j'ai annoncé une application Web appelée Weather Data Map sur github. La distribution météorologique est affichée sur Google Maps, et vous pouvez voir librement la distribution des tendances à chaque point. Essayez-le.