全排列算法的实现

题目如下：
a）求一个全排列函数：如p([1,2,3]) ，输出：  [123],[132],[213],[231],[321],[323]。
b）求一个组合函数：    如p([1,2,3]) ，输出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]。

排列的解法

void GetArray(int* a,int left,int right)
{
	int i;
//	cout<<left <<right<<endl;
	if( right <= left )
	{
		for(i=0;i<right;++i)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
	}
	else
	{
		for(i=left; i<right;++i)
		{
			swap(a[i],a[left]);
			GetArray(a,left+1,right);
			swap(a[i],a[left]);
		}
	}
}

组合想了好久没想出思路，求指导啊！！

评论

3 楼 zhc0822 2011-11-25  

ZeaLoVe 写道

zhc0822 写道

用js写了一个。
思路是先快排一遍，然后依次将数组的每个元素EnQueue。
接着创建一个新数组，每次DeQueue之前，先遍历一遍队列，将当前队列中的元素依次加入之前创建的新数组，每次加入之前输出一遍数组的内容。
直到队列为空，程序终止。

var queue=[1,2,3]; // 先快排一遍，然后依次将数组的每个元素EnQueue，此处省略
do{     
    var temp=[]; //创建一个数组
    for(var i=0; i!=arr.length; i++){
         temp.push(arr[i]);         
         console.log(temp);     
    }      
    queue.shift(); // Dequeue
}while(queue.length>0) 

output:
[1]
[1, 2]
[1, 2, 3]
[2]
[2, 3]
[3]

你这个算法有问题啊。。漏了1，3.。。如果数据量大起来还会漏更多的

好吧，是我想简单了。搞了一个比较水的版本。
思路是构建上三角矩阵，比如{{1,2,3},{0,2,3},{0,0,3}}
然后只取对角线上的元素压栈。

var matrix=[[1,2,3,4],[0,2,3,4],[0,0,3,4],[0,0,0,4]]; 
//var matrix=[[1,2,3],[0,2,3],[0,0,3]];
function calc(arr, index){
    for(var i=index; i<matrix.length; i++){
        var temp=[];
        for(var j=0; j!=arr.length; j++){
            temp.push(arr[j]);
        }
        temp.push(matrix[i][i]);
        console.log(temp);
        calc(temp,i+1);
    }
}
calc([], 0);

output:
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 4]
[1, 3]
[1, 3, 4]
[1, 4]
[2]
[2, 3]
[2, 3, 4]
[2, 4]
[3]
[3, 4]
[4]

2 楼 ZeaLoVe 2011-11-24  

zhc0822 写道

用js写了一个。
思路是先快排一遍，然后依次将数组的每个元素EnQueue。
接着创建一个新数组，每次DeQueue之前，先遍历一遍队列，将当前队列中的元素依次加入之前创建的新数组，每次加入之前输出一遍数组的内容。
直到队列为空，程序终止。

var queue=[1,2,3]; // 先快排一遍，然后依次将数组的每个元素EnQueue，此处省略
do{     
    var temp=[]; //创建一个数组
    for(var i=0; i!=arr.length; i++){
         temp.push(arr[i]);         
         console.log(temp);     
    }      
    queue.shift(); // Dequeue
}while(queue.length>0) 

output:
[1]
[1, 2]
[1, 2, 3]
[2]
[2, 3]
[3]

你这个算法有问题啊。。漏了1，3.。。如果数据量大起来还会漏更多的

1 楼 zhc0822 2011-11-24  

用js写了一个。
思路是先快排一遍，然后依次将数组的每个元素EnQueue。
接着创建一个新数组，每次DeQueue之前，先遍历一遍队列，将当前队列中的元素依次加入之前创建的新数组，每次加入之前输出一遍数组的内容。
直到队列为空，程序终止。

var queue=[1,2,3]; // 先快排一遍，然后依次将数组的每个元素EnQueue，此处省略
do{     
    var temp=[]; //创建一个数组
    for(var i=0; i!=arr.length; i++){
         temp.push(arr[i]);         
         console.log(temp);     
    }      
    queue.shift(); // Dequeue
}while(queue.length>0) 

output:
[1]
[1, 2]
[1, 2, 3]
[2]
[2, 3]
[3]