Nice to meet you all. My name is Yuji Miyane. This is Qiita's debut.
Now there is the problem of inspecting all combinations of elements to find the optimal solution, which can generally be solved by applying a permutation search algorithm to generate permutation combinations.
In mathematical terms, "all combinations of 5 to 3 in order" is "permutation", and "combination of 5 to 3 in any order" is "combination". Only permutations are shown here.
This generation feature is included in many high-level language standard libraries. In Ruby, the Array class has a built-in permutation method.
$ 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 has an itertool module in its standard library.
$ 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)]
But JavaScript doesn't. If you look for an external library, it seems to be somewhere, but I couldn't find it, so I made it myself (please use it).
(Supplement) I found the node.js version of itertools in Python when I searched later, so I will introduce it.
I'll show you the code and how to use it first, and then explain what it does.
I currently write all JavaScript in CoffeeScript, and initially created the CoffeeScript version.
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
Based on the results of compiling the CoffeeScript code, the following JavaScript code has been manually optimized with a little 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;
};
})();
When this is executed (loaded), a permutation method is added to the Array object, and it can be called from the Array object as follows (it can be called with the same method name and format as ruby).
[0, 1, 2].permutation()
// -> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
If you just want to use the code, this is enough to read. Feel free to use it.
Below is a description of the code. It's short, but I use various techniques. First, the outermost anonymous function locks the var variable inside it (keeping it out) and executes it only once (one of the common JavaScript techniques).
(function() {
var generatePermutation = ...
// use as a local variable })(); // Here generatePermutation is undefined
The heart is the generatePermutation function (which has only 10 rows in effect but is fairly dense). Let's start with the following standard techniques (intermediate and above will not need to explain).
post.slice (0) makes a duplicate of the array: There are several other ways to use concat
post.concat([])[].concat(post)post.concat () is also possible, but may not be available in older browsersrest.splice (i, 1) extracts the i-th array and shrinks the array (destruction processing), and returns the array of the extracted elements (1 in this case).pre.concat (elem) creates a new array with elem concatenated after it (non-destructive)Recursive processing is required to generate permutation combinations. This is the true heart, so I will explain it in detail. Let's set the array to be processed as [0, 1, 2, 3], and show how the arguments (pre, post) passed to the first level change.
[0, 1, 2, 3]
[0], [1, 2, 3] // State of arguments pre, post (same below) [1], [0, 2, 3] [2], [0, 1, 3] [3], [0, 1, 2]
This is the first level, one element is extracted in order, moved to the beginning, and the remaining elements are processed recursively. Recurse while decrementing the recursion level (n) by one, and when it reaches 0, add it to the final result (perm). The flow of recursion processing when the beginning is 0 is shown (the maximum recursion level is 3 and there are 6 ways in 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]
... and so on ...
The important thing here is whether the method is destructive (modifies itself) or non-destructive (creates a new array), and since splice is a destructive method, you need to make a duplicate with slice (0) in advance. ..
Finally, register this in the permutation property of Array.prototype and include it in the Array object. This is a well-known JavaScript technique, so I won't explain it here.
Array.prototype.permutation = function(n) {
if (n == null) n = this.length;
var perm = [];
generatePermutation(perm, [], this, n);
return perm;
};
One last word. The other day, I announced a web application called Weather Data Map on github. The weather distribution is displayed on Google Maps, and you can freely see the trend distribution at each point. Please try it.