JavaScriptの全配列の六種類のアルゴリズムは具体的に実現します.
13492 ワード
全部並べられているのは時間の複雑さです.O(n!)のアルゴリズムは先日学生に講義しました.この問題を考えて帰ってきてまとめました.7つのアルゴリズムで解決できます.その中でダイナミックサイクルはトレースアルゴリズムに似ています.すべてのアルゴリズムはJavaScriptを使って作成され、直接実行できます.
アルゴリズム1:交換(再帰)
アルゴリズム1:交換(再帰)
Full Permutation(Recursive Swap) - Mengliao Software
Full Permutation(Recursive Swap)
Mengliao Software Studio - Bosun Network Co., Ltd.
2011.05.24
<br>/*
<br> （ ）
<br>1、 ；
<br>2、 （ ）；
<br>3、 。
<br>*/
<br>function swap(arr,i,j) {
<br> if(i!=j) {
<br> var temp=arr[i];
<br> arr[i]=arr[j];
<br> arr[j]=temp;
<br> }
<br>}
<br>var count=0;
<br>function show(arr) {
<br> document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
<br>}
<br>function perm(arr) {
<br> (function fn(n) { // n
<br> for(var i=n;i<arr.length;i++) {
<br> swap(arr,i,n);
<br> if(n+1<arr.length-1) // 1
<br> fn(n+1); // n+1
<br> else
<br> show(arr); //
<br> swap(arr,i,n);
<br> }
<br> })(0);
<br>}
<br>perm(["e1","e2","e3","e4"]);
<br>
Full Permutation(Recursive Link) - Mengliao Software
Full Permutation(Recursive Link)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
<br>/*
<br> （ ）
<br>1、 ， （ ）；
<br>2、 （ ）；
<br>3、 （ ）；
<br>4、 2、3， ， 。
<br>*/
<br>var count=0;
<br>function show(arr) {
<br> document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
<br>}
<br>function perm(arr) {
<br> (function fn(source, result) {
<br> if (source.length == 0)
<br> show(result);
<br> else
<br> for (var i = 0; i < source.length; i++)
<br> fn(source.slice(0, i).concat(source.slice(i + 1)), result.concat(source[i]));
<br> })(arr, []);
<br>}
<br>perm(["e1", "e2", "e3", "e4"]);
<br>
Full Permutation(Recursive Backtrack) - Mengliao Software
Full Permutation(Recursive Backtrack)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
<br>/*
<br> （ ）
<br>1、 ， ， ；
<br>2、 ， n ；
<br>3、 n 。
<br>*/
<br>var count = 0;
<br>function show(arr) {
<br> document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
<br>}
<br>function seek(index, n) {
<br> if (n >= 0) // ，
<br> if (index[n] < index.length - 1) { //
<br> index[n]++; //
<br> if ((function () { //
<br> for (var i = 0; i < n; i++)
<br> if (index[i] == index[n]) return true; //
<br> return false; //
<br> })())
<br> return seek(index, n); //
<br> else
<br> return true; //
<br> }
<br> else { // ，
<br> index[n] = -1; //
<br> if (seek(index, n - 1)) //
<br> return seek(index, n); //
<br> else
<br> return false; //
<br> }
<br> else
<br> return false;
<br>}
<br>function perm(arr) {
<br> var index = new Array(arr.length);
<br> for (var i = 0; i < index.length; i++)
<br> index[i] = -1; // -1， ++ 0
<br> for (i = 0; i < index.length - 1; i++)
<br> seek(index, i); // n-1
<br> while (seek(index, index.length - 1)) { // n ，
<br> var temp = [];
<br> for (i = 0; i < index.length; i++) //
<br> temp.push(arr[index[i]]);
<br> show(temp);
<br> }
<br>}
<br>perm(["e1", "e2", "e3", "e4"]);
<br>
Full Permutation(Non-recursive Backtrack) - Mengliao Software
Full Permutation(Non-recursive Backtrack)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
<br>/*
<br> （ ）
<br>1、 ， ， ；
<br>2、 n 。
<br>*/
<br>var count = 0;
<br>function show(arr) {
<br> document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
<br>}
<br>function seek(index, n) {
<br> var flag = false, m = n; //flag ，m
<br> do {
<br> index[n]++;
<br> if (index[n] == index.length) //
<br> index[n--] = -1; // ，
<br> else if (!(function () {
<br> for (var i = 0; i < n; i++)
<br> if (index[i] == index[n]) return true;
<br> return false;
<br> })()) //
<br> if (m == n) //
<br> flag = true;
<br> else
<br> n++;
<br> } while (!flag && n >= 0)
<br> return flag;
<br>}
<br>function perm(arr) {
<br> var index = new Array(arr.length);
<br> for (var i = 0; i < index.length; i++)
<br> index[i] = -1;
<br> for (i = 0; i < index.length - 1; i++)
<br> seek(index, i);
<br> while (seek(index, index.length - 1)) {
<br> var temp = [];
<br> for (i = 0; i < index.length; i++)
<br> temp.push(arr[index[i]]);
<br> show(temp);
<br> }
<br>}
<br>perm(["e1", "e2", "e3", "e4"]);
<br>
Full Permutation(Non-recursive Sort) - Mengliao Software
Full Permutation(Non-recursive Sort)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.30
<br>/*
<br> （ ）
<br>1、 ， ， ；
<br>2、 ：
<br> P 1～n( ) ：p = p1,p2...pn = p1,p2...pj-1,pj,pj+1...pk-1,pk,pk+1...pn
<br>(1) ， j（j ）， j = max{i | pi < pi+1}
<br>(2) pj ， pj k， k = max{i | pi > pj}
<br> pj ， k pj
<br>(3) pj pk
<br>(4) pj+1...pk-1,pk,pk+1...pn p' = p1,p2...pj-1,pj,pn...pk+1,pk,pk-1...pj+1
<br>(5)p' p
<br>
<br> ：
<br>24310 0～4 ， ：
<br>(1) 2；
<br>(2) 2 3；
<br>(3) 2 3 34210；
<br>(4) 2（ 3） ， 4210， 30124；
<br>(5) 24310 30124。
<br>*/
<br>var count = 0;
<br>function show(arr) {
<br> document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
<br>}
<br>function swap(arr, i, j) {
<br> var t = arr[i];
<br> arr[i] = arr[j];
<br> arr[j] = t;
<br>
<br>}
<br>function sort(index) {
<br> for (var j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--)
<br> ; // ， ， j
<br> if (j < 0) return false; //
<br> for (var k = index.length - 1; index[k] < index[j]; k--)
<br> ; // ， j ， k
<br> swap(index, j, k);
<br> for (j = j + 1, k = index.length - 1; j < k; j++, k--)
<br> swap(index, j, k); // j+1
<br> return true;
<br>}
<br>function perm(arr) {
<br> var index = new Array(arr.length);
<br> for (var i = 0; i < index.length; i++)
<br> index[i] = i;
<br> do {
<br> var temp = [];
<br> for (i = 0; i < index.length; i++)
<br> temp.push(arr[index[i]]);
<br> show(temp);
<br> } while (sort(index));
<br>}
<br>perm(["e1", "e2", "e3", "e4"]);
<br>
Full Permutation(Non-recursive Modulo) - Mengliao Software
Full Permutation(Non-recursive Modulo)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
<br>/*
<br> （ ）
<br>1、 result， ；
<br>2、 n ， n!；
<br>3、 >=0 n! ， 1， index；
<br>4、 1 arr[0]， 1 ， index 1 w， 1 （arr[0]） result w ， index index\1；
<br>5、 2 arr[1]， 2 ， index 2 w， 2 （arr[1]） result w ， index index\2；
<br>6、 3 arr[2]， 3 ， index 3 w， 3 （arr[2]） result w ， index index\3；
<br>7、……
<br>8、 arr[arr.length-1]， ；
<br>9、 index ， 。
<br>
<br> ：
<br> 4 ["a", "b", "c", "d"] , 4!=24 ， >=0 index ， 1， index+23 ；
<br> index=13（ 13+24，13+2*24，13+3*24…）， 4 ， 4 ， ：
<br> 1 ，13/1， =13， =0， 1 0 （ 0）， ["a"]；
<br> 2 ，13/2, =6， =1， 2 1 （ 1）， ["a", "b"]；
<br> 3 ，6/3, =2， =0， 3 0 （ 0）， ["c", "a", "b"]；
<br> 4 ，2/4， =0， =2, 4 2 （ 2）， ["c", "a", "d", "b"]；
<br>*/
<br>var count = 0;
<br>function show(arr) {
<br> document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
<br>}
<br>function perm(arr) {
<br> var result = new Array(arr.length);
<br> var fac = 1;
<br> for (var i = 2; i <= arr.length; i++)
<br> fac *= i;
<br> for (index = 0; index < fac; index++) {
<br> var t = index;
<br> for (i = 1; i <= arr.length; i++) {
<br> var w = t % i;
<br> for (j = i - 1; j > w; j--)
<br> result[j] = result[j - 1];
<br> result[w] = arr[i - 1];
<br> t = Math.floor(t / i);
<br> }
<br> show(result);
<br> }
<br>}
<br>perm(["e1", "e2", "e3", "e4"]);
<br>