Specific implementation of six algorithms for JavaScript full arrangement_javascript skills

Total permutation is an algorithm with a time complexity of: O(n!). I was giving a lecture to students two days ago and I accidentally thought of this problem. I came back and summarized it. It can be solved by 7 algorithms, among which dynamic loops are similar to backtracking algorithms. It is relatively cumbersome to implement, so I have summarized 6 types for the convenience of readers. All algorithms are written in JavaScript and can be run directly.
Algorithm 1: Exchange (recursion)

Copy code The code is as follows:

Full Permutation(Recursive Swap)

Mengliao Software Studio - Bosun Network Co., Ltd.

2011.05.24

Algorithm 2: Linking (recursive)

Copy code

The code is as follows:

Full Permutation(Recursive Link)

Mengliao Software Studio - Bosun Network Co., Ltd.

2012.03.29

Algorithm 3: Backtracking (recursion) >

Copy code

The code is as follows:

Full Permutation(Recursive Backtrack)

Mengliao Software Studio - Bosun Network Co., Ltd.

2012.03.29

Algorithm 4: Backtracking (non-recursive)





Copy code

The code is as follows:

< ;body>

2012.03.29

Algorithm 5: Sorting (non-recursive)

Copy code

The code is as follows:

< ;body> 2012.03.30

Algorithm 6: Modulo (non-recursive)

Copy code

The code is as follows:

< ;body>

Full Permutation (Non-recursive Modulo)
;/p> Is equal to the number of elements in the original array;
2. Calculate the total number of all n elements arranged, that is, n!;
3. Loop n! times starting from any integer >=0, accumulating 1 each time , recorded as index;
4. Take the first element arr[0], find the lowest bit of the 1-digit expression, that is, find the value w of index modulo 1, and insert the first element (arr[0]) w position of result, and iterate index to index1;
5. Take the second element arr[1], find the lowest bit of the binary expression, that is, find the value w of index modulo 2, and change the second element (arr[1]) Insert the w position of result, and iterate index to index2;
6. Take the third element arr[2] and find the lowest bit of the ternary expression, that is, find the value of index modulo 3 w, insert the third element (arr[2]) into the w position of result, and iterate the index to index3;
7,...
8, until the last element arr[arr.length-1 is taken ], at this time a permutation is obtained;
9. When the index loop is completed, all permutations are obtained.

Example:
Find the full arrangement of 4 elements ["a", "b", "c", "d"], loop 4!=24 times in total, and can start from any>= The integer index of 0 starts the loop, accumulating 1 each time, until it ends after the loop reaches index 23;
Assume index=13 (or 13 24, 13 2*24, 13 3*24...), because there are 4 elements in total, Therefore, after iterating 4 times, the resulting permutation process is:
The 1st iteration, 13/1, quotient = 13, remainder = 0, so the 1st element is inserted into the 0th position (that is, the subscript is 0), get ["a"];
The second iteration, 13/2, quotient=6, remainder=1, so the second element is inserted into the first position (that is, the subscript is 1), and we get [ "a", "b"];
The 3rd iteration, 6/3, quotient=2, remainder=0, so the 3rd element is inserted into the 0th position (that is, the subscript is 0), and we get [" c", "a", "b"];
The 4th iteration, 2/4, quotient=0, remainder=2, so the 4th element is inserted into the 2nd position (that is, the subscript is 2), Get ["c", "a", "d", "b"];
*/
var count = 0;
function show(arr) {
document.write("P< ;sub>" count ": " arr "
");
}
function perm(arr) {
var result = new Array(arr.length) ;
var fac = 1;
for (var i = 2; i <= arr.length; i )
fac *= i;
for (index = 0; index < fac ; index ) {
var t = index;
for (i = 1; i <= arr.length; i ) {
var w = t % i;
for (j = i - 1; j > w; j--)
result[j] = result[j - 1];
result[w] = arr[i - 1];
t = Math.floor (t / i);
} }
show(result);
}
}
perm(["e1", "e2", "e3", "e4"]);





Some of the above six algorithms are to arrange positions, such as backtracking, sorting, etc. , because this can adapt to various types of elements, rather than requiring that the elements to be arranged must be numbers or letters, etc.