生成1~n的排列

最近看了下全排列问题,感觉还好,有些意思,大多数实现都是使用的递归的思想,数学的思路是取低一位的全排列,比如123,就是1和2,3的全排列,1234,是1234和234的全排列,234的全排列又是2和23的全排列等等,正好是一个递归。正巧在书上看到一个C语言版的实现,看了下,用JS实现如下。

                  function print_permutation(n,arr,cur){
			var i,j;
			if(cur === n){  //递归边界
				var temp = "";
				for(i = 0;i < n;i++){
					temp+=arr[i];
				}
				$.log(temp+"<br />");
			}else{
				for(i = 1;i<=n;i++){
					var ok = 1;
					for(j = 0;j<cur;j++){
						if( arr[j] === i ) ok = 0;
					}
					if(ok){
						arr[cur] = i;
						print_permutation(n,arr,cur+1);
						
					}
				}
			}
		}
		print_permutation(n,[],0)

不过因为全排列的总数是阶乘,而且递归有性能的损耗。就拿小一点的数字来demo了。比如n=4的时候。全排列还有其他问题,有空继续看。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据