全排列是一种时间复杂度为:O(n!)的算法。所有算法均使用JavaScript编写,可直接运行。 算法一:循环,一组排列需要几个元素就用几个for(比较笨拙的方法)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | <script type= "text/javascript" >
var str= "01,02,03,04" ;
var strArray=str.split( "," );
var len=strArray.length;
var newArray= new Array();
for ( var i=0;i<len;i++){
for ( var j=0;j<len;j++){
if (j!=i){
for ( var k=0;k<len;k++){
if (k!=i && k!=j){
for ( var l=0;l<len;l++){
if (l!=i && l!=j && l!=k){
newArray.push(strArray[i]+ " " +strArray[j]+ " " +strArray[k]+ " " +strArray[l]);
}
}
}
}
}
}
}
var len2=newArray.length;
document.write( "排列方式种类有:" + len2 + " 种<br />" );
for (i=0;i<len2;i++){
document.write(newArray[i] + "<br />" );
}
</script>
|
算法二:交换算法(递归)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | <script type= "text/javascript" >
function swap(arr,i,j) {
if (i!=j) {
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
var count=0;
function show(arr) {
document.write( "P<sub>" + ++count+ "</sub>: " +arr+ "<br />" );
}
function perm(arr) {
( function fn(n) {
for ( var i=n;i<arr.length;i++) {
swap(arr,i,n);
if (n+1<arr.length-1)
fn(n+1);
else
show(arr);
swap(arr,i,n);
}
})(0);
}
perm([ "01" , "02" , "03" , "04" ]);
</script>
|
算法三:链接算法(递归) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | <script type= "text/javascript" >
var count=0;
function show(arr) {
document.write( "P<sub>" + ++count+ "</sub>: " +arr+ "<br />" );
}
function perm(arr) {
( function fn(source, result) {
if (source.length == 0)
show(result);
else
for ( var i = 0; i < source.length; i++)
fn(source.slice(0, i).concat(source.slice(i + 1)), result.concat(source[i]));
})(arr, []);
}
perm([ "01" , "02" , "03" , "04" ]);
</script>
|
算法四:回溯算法(递归) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | <script type= "text/javascript" >
var count = 0;
function show(arr) {
document.write( "P<sub>" + ++count + "</sub>: " + arr + "<br />" );
}
function seek(index, n) {
if (n >= 0)
if (index[n] < index.length - 1) {
index[n]++;
if (( function () {
for ( var i = 0; i < n; i++)
if (index[i] == index[n]) return true ;
return false ;
})())
return seek(index, n);
else
return true ;
}
else {
index[n] = -1;
if (seek(index, n - 1))
return seek(index, n);
else
return false ;
}
else
return false ;
}
function perm(arr) {
var index = new Array(arr.length);
for ( var i = 0; i < index.length; i++)
index[i] = -1;
for (i = 0; i < index.length - 1; i++)
seek(index, i);
while (seek(index, index.length - 1)) {
var temp = [];
for (i = 0; i < index.length; i++)
temp.push(arr[index[i]]);
show(temp);
}
}
perm([ "01" , "02" , "03" , "04" ]);
</script>
|
算法五:回溯算法(非递归) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | <script type= "text/javascript" >
var count = 0;
function show(arr) {
document.write( "P<sub>" + ++count + "</sub>: " + arr + "<br />" );
}
function seek(index, n) {
var flag = false , m = n;
do {
index[n]++;
if (index[n] == index.length)
index[n--] = -1;
else if (!( function () {
for ( var i = 0; i < n; i++)
if (index[i] == index[n]) return true ;
return false ;
})())
if (m == n)
flag = true ;
else
n++;
} while (!flag && n >= 0)
return flag;
}
function perm(arr) {
var index = new Array(arr.length);
for ( var i = 0; i < index.length; i++)
index[i] = -1;
for (i = 0; i < index.length - 1; i++)
seek(index, i);
while (seek(index, index.length - 1)) {
var temp = [];
for (i = 0; i < index.length; i++)
temp.push(arr[index[i]]);
show(temp);
}
}
perm([ "01" , "02" , "03" , "04" ]);
</script>
|
算法六:排序算法(非递归) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | <script type= "text/javascript" >
var count = 0;
function show(arr) {
document.write( "P<sub>" + ++count + "</sub>: " + arr + "<br />" );
}
function swap(arr, i, j) {
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
function sort(index) {
for ( var j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--)
;
if (j < 0) return false ;
for ( var k = index.length - 1; index[k] < index[j]; k--)
;
swap(index, j, k);
for (j = j + 1, k = index.length - 1; j < k; j++, k--)
swap(index, j, k);
return true ;
}
function perm(arr) {
var index = new Array(arr.length);
for ( var i = 0; i < index.length; i++)
index[i] = i;
do {
var temp = [];
for (i = 0; i < index.length; i++)
temp.push(arr[index[i]]);
show(temp);
} while (sort(index));
}
perm([ "01" , "02" , "03" , "04" ]);
</script>
|
算法七:求模算法(非递归) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | <script type= "text/javascript" >
var count = 0;
function show(arr) {
document.write( "P<sub>" + ++count + "</sub>: " + arr + "<br />" );
}
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([ "01" , "02" , "03" , "04" ]);
</script>
|
上面的7种算法有些是对位置进行排列,例如回溯、排序等,因为这样可以适应各种类型的元素,而非要求待排列元素一定是数字或字母等。 文章出处 http://www./post/134.html
|