`
ZeaLoVe
  • 浏览: 91583 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

全排列算法的实现

 
阅读更多
题目如下:
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]

相关推荐

    全排列算法实现(java\c#\c++,各种主流语言版本)

    全排列算法是计算机科学中的一种基础算法,它用于找出给定集合的所有可能的排列组合。在本例中,我们将讨论如何使用递归方法实现全排列,以Java、C#、...在实际应用中,可以根据具体需求和性能要求选择合适的算法实现。

    全排列算法实现(C)

    实现全排列组合的算法,供大家学习与参考。在需要对排列组合做差异分析的时候可以直接使用。例如:几个正则式的不同排列组合对匹配效果的影响

    全排列算法解析(完整版)

    在C++中,标准模板库(STL)提供了next_permutation()函数,可以用来直接生成下一个排列,极大地方便了排列组合的算法实现。 对于时间复杂度,全排列算法至少是O(n!)的复杂度,因为需要生成所有可能的排列组合。...

    全排列算法部分算法需要自己优化修改

    总结,全排列算法主要通过递归或迭代实现,利用深度优先搜索或回溯策略。优化方法包括剪枝和记忆化,以减少重复计算和提高效率。对于具体的问题,需要根据实际需求和数据规模选择合适的实现方式。在编程实践中,理解...

    全排列算法 实例 一种实现了n个数全排列的算法

    下面是一个基于回溯法的全排列算法的Python实现: ```python def permute(nums): res = [] def backtrack(first=0): if first == len(nums): res.append(nums[:]) for i in range(first, len(nums)): nums...

    全排列算法 全排列算法 (c#版)

    在C#编程语言中,实现全排列算法可以帮助开发者解决多种问题,例如组合优化、数据排序等。本篇文章将深入探讨全排列算法的原理、C#实现方法以及相关的应用。 全排列算法的基本思想是回溯法,通过递归或迭代的方式,...

    一种计算全排列的简易算法

    在给定的标题“一种计算全排列的简易算法”中,我们可以推测这是一种简化版的全排列算法实现。全排列算法通常有多种实现方式,例如深度优先搜索(DFS)、回溯法、栈或者队列等。这种简易算法可能是通过递归或迭代的...

    全排列算法解析(完整版)

    ### 全排列算法解析 #### 1. 全排列的定义和公式 全排列是指从一个包含`n`个不同元素的集合中选取全部`n`个元素,并按一定顺序排列形成的不同序列总数。数学上,`n`个不同元素的全排列数记为`n!`(`n`的阶乘),即...

    利用中介数实现全排列算法

    利用中介数实现全排列算法,采用java实现。

    C语言实现的全排列算法

    在本例中,我们讨论的是使用C语言实现的全排列算法,主要关注递归方法。 在C语言中,全排列的实现通常基于回溯法。回溯法是一种试探性的解决问题的方法,它尝试分步地构造解决方案,并在每一步选择时,如果发现当前...

    组合数学全排列算法(转)

    根据提供的信息来看,实际文章内容并未直接包含关于组合数学中的全排列算法的详细解析,而是主要介绍了清华大学计算机科学与技术系的一些活动与新生入学情况。不过,既然题目要求围绕组合数学中的全排列算法进行展开...

    深入全排列算法及其实现方法

    全排列在很多程序都有应用,是一个很常见的算法,常规的算法是一种递归的算法,这种算法的得到基于以下的分析思路。 给定一个具有n个元素的集合(n&gt;=1),要求输出这个集合中元素的所有可能的排列。一、递归实现...

    全排列(多种算法实现)

    下面将详细介绍几种不同的全排列算法实现: 1. **深度优先搜索(DFS)** 深度优先搜索是一种用于遍历或搜索树或图的算法。在全排列问题中,我们可以用回溯法配合DFS来实现。基本步骤如下: - 从序列的第一个元素...

    objective-c数组全排列算法

    下面,我们将详细探讨如何使用Objective-C实现全排列算法,并通过数组保存结果。 首先,我们需要定义一个数组来存储原始数据,然后创建一个方法来处理全排列。这个方法将接收两个参数:一是原始数组,二是用于保存...

    组合数学全排列算法

    实现了字典序法、递增进位制数法、递减进位制数法、邻位对换法四种全排列算法。全排列算法有很多种,这里只是其中的一些,可以调试运行比较一下各种算法的效率。(该代码为初级版本,注重算法的实现,在交互方面需要...

    c#全排列的算法

    在C#中,可以使用递归或迭代的方式来实现全排列算法。 在给定的代码中,我们可以看到,作者使用了递归的方式来实现全排列算法。该算法的主要思想是,从原始数组中选择指定数量的元素,生成所有可能的排列方式。例如...

    全排列算法设计分析.ppt

    全排列算法设计分析主要关注如何生成一个序列中所有可能的不同排列。全排列是指从n个不同元素中取出m个元素,按照一定的顺序排列起来,所有可能的...通过理解和实现全排列算法,我们可以更有效地处理多元素组合的问题。

    Python字符串的全排列算法实例详解

    在本篇文章中,我们将通过一个具体的例子来详细介绍如何使用Python语言实现字符串的全排列算法,并深入探讨其中的细节。 #### 二、全排列的基本概念 全排列是指在一个集合中取出所有元素的所有不同排列方式。例如,...

    使用javascript写的全排列算法演示(分为回溯法演示和交换法演示)

    在提供的压缩包中,`index.html`文件很可能是展示这两种算法实现的网页。打开这个文件,你可以看到实际的代码示例,以及可能的交互界面,让你能够直观地理解这两种方法如何工作。通过分析和运行这些代码,你可以更好...

    排列组合的全排列算法(交换算法)

    全排列算法是计算机科学中处理数组或集合的一种经典方法,主要应用于组合数学和算法设计领域。在本场景中,我们关注的是"交换算法",它用于生成一个给定数组的所有可能排列。全排列是指从n个不同元素中取出m个元素...

Global site tag (gtag.js) - Google Analytics