`
ooaer
  • 浏览: 138582 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

全排列的新思路

    博客分类:
  • C++
阅读更多
以前 编过 一个 小程序 是 全排列的 递归算法;
#include<iostream>
using namespace std;
int arr[10];
void swap(int i,int j)
{
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp; 
}
void perm(int k,int m)
{
	int i;
  if(k==m)
  {
    for(i=0;i<=m;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
  }
  else
  {
    for(i=k;i<=m;i++)
	{
	  swap(k,i);
	  perm(k+1,m);
	  swap(k,i);
	}
  
  }
}
int main()
{
 for(int i=0;i<10;i++)
	 arr[i] = i+1;
 perm(0,3);
for( i=0;i<10;i++)
   cout<<arr[i]<<" ";
return 0;
}


最近看一些数据结构的 书籍,看到 图论 里面有个 哈密顿回路问题,想想 好像 如果给定的图是 全联通图的 话 那么 经过 该算法 所输出的 也就是 全排列 问题,当然 这只是 一种哈密顿的特殊情况罢了

贴一下 代码,先贴个 递归的吧:
#include<iostream>
using namespace std;
int arr[10][10];
int s[10];
int visited[10];
int count = 0;
int n;
void dfs(int k)
{
	visited[k]=1;s[count++]=k;
  
  if(n==count)
  {
	  for(int j=0;j<n;j++)
		  cout<<s[j]<<" ";
      cout<<endl;w
  }
  for(int i=0;i<n;i++)
  {
     if(arr[k][i]&&!visited[i])
		 dfs(i);
  }
  visited[k] = 0;
  count--;


}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>arr[i][j];
 for( i=0;i<n;i++)
	 dfs(i);
return 0;
}

分享到:
评论

相关推荐

    全排列的Hash函数(JAVA)

    由于无法直接访问该链接,以下将提供一个通用的全排列和Hash函数的实现思路: 1. **全排列的实现**: - 使用递归或回溯法。首先,选择一个元素作为排列的第一个位置,然后对剩下的元素进行全排列。 - 递归函数的...

    全排列——递归排序和字典序列

    其基本思路是从集合中依次选取每一个元素作为排列的第一个元素,然后对剩下的元素继续进行全排列,直到所有元素都被排列完成。这种方法利用了递归的特性,不断地分解问题直至达到最简单的基本情况,然后再逐步回溯...

    全排列的算法 翻转法 换位法 字典序法

    基本思路是从第一个元素开始,每次选择一个未使用的元素放置在当前排列的末尾,然后递归地对剩余元素进行全排列。当所有元素都被使用过且已形成一个合法排列时,返回结果。在递归过程中,若发现无法找到合适的元素,...

    qpl.rar_CC_全排列_输入全排列

    通过这个C++源代码,学习者可以理解如何运用递归和回溯法解决全排列问题,这对于理解和掌握算法设计思路,尤其是面对复杂问题的求解策略,具有很大的帮助。同时,这也是编程实践中提升问题解决能力的一个典型实例。

    N个数全排列的非递归算法

    全排列非递归算法的核心思路通常包括以下步骤: 1. **初始化**:创建一个大小为n的数组,存放原始的n个数字,并创建一个大小为n!的存储空间,用于存储所有可能的排列结果。 2. **遍历**:使用循环结构,例如使用两...

    quanpailie.rar_C++quanpailie_quanpailiec++_一组数全排列_全排列

    总结来说,C++中的全排列算法主要通过回溯法和递归法实现,这两种方法都是基于尝试所有可能性并及时回溯的思路。理解并掌握全排列算法,有助于提升编程解决组合问题的能力。在实际项目中,根据具体需求和性能要求,...

    全排列算法设计分析.ppt

    另一种方法是使用回溯法,从序列的第一个元素开始,尝试将每个元素放到首位并生成新的子序列,然后对子序列进行全排列,如果达到预期的排列数则回溯到上一步,尝试下一个可能的元素。 总之,全排列算法设计分析是...

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

    根据以上思路,我们可以编写如下的Python代码来实现字符串的全排列功能: ```python class Solution: def permutation(self, ss): # 定义递归函数 def recurPermutation(ss, index): result = [] if index == ...

    python递归全排列实现方法

    这种递归解决方案的优点是思路清晰,易于理解,但缺点是效率较低,因为它会产生大量的重复交换操作,特别是对于较大的输入。为了提高效率,可以考虑使用其他算法,如回溯法,通过剪枝减少不必要的计算。然而,对于...

    Golang排列组合算法问题之全排列实现方法

    通过这个例子,我们可以了解到Golang中实现全排列算法的基本思路和步骤,包括递归、字符串操作和排序。这种算法在处理各种排列组合问题时非常有用,例如解决火车出站顺序、字符组合等问题。理解并熟练掌握全排列算法...

    全排列和棋盘覆盖的java实现代码

    递归的基本思路是,对于n个元素的全排列问题,我们先选择一个元素作为排列的第一个,然后对剩下的n-1个元素进行全排列。这样,每次递归调用都会解决规模更小的问题,直到问题规模缩小到只剩下一个元素或为空,此时...

    python非递归全排列实现方法

    ##### 2.3 函数设计思路 1. **`getArrayInsertCharToStr(STR, CHAR)`**: 此函数接收两个参数,一个字符串`STR`和一个字符`CHAR`,返回的是`CHAR`插入到`STR`中每个位置所形成的新字符串列表。 ```python def ...

    js实现字符全排列算法的简单方法

    具体算法思路是利用递归和正则表达式来实现。首先,函数charsMap接收一个字符串参数o,然后对这个字符串进行处理,去除其中的重复字符和空白字符。接着,通过判断字符串的长度,以递归的方式进行处理: 1. 当字符串...

    python3实现字符串的全排列的方法(无重复字符)

    这两种方法虽然在实现细节上有所不同,但其核心思路都是通过递归处理字符串的未排序部分,从而生成所有可能的排列。第一种方法是通过拆分字符串并逐个添加第一个字符,而第二种方法则是通过不断交换字符位置来生成新...

    php求数组全排列,元素所有组合的方法总结

    这里采用的是基于比较的算法,主要利用了冒泡排序的思路,通过不断调整数组元素的顺序来生成新的排列。 以下是对代码的详细解释: 1. 定义源数组$source,确保其元素有序。这里使用`sort()`函数对数组进行排序,...

    全排序问题分析及程序

    对于`n&gt;1`的情况,`perm(R)`可以由`r1`到`rn`分别与`R1`到`Rn`的全排列组合而成,这就形成了递归的解题思路。 在提供的代码中,`Perm`函数是一个递归函数,用于生成给定列表`list`中从索引`0`到`k-1`的元素作为前缀...

    quanpailie.rar_数组排列组合

    2. 对于剩下的元素,递归地对剩余部分进行全排列,将首位与剩余部分的每一个全排列组合,形成新的排列。 3. 当没有剩余元素时,表示完成一个全排列,将其记录或输出。 4. 递归返回上一层,继续尝试其他可能的首位。 ...

    整数数组的全排算法,很经典!!!

    - 基本思路是先固定第一个元素,然后对剩下的元素进行全排列,直到数组为空。 - 例如,对于数组[1, 2, 3],先固定1,然后对[2, 3]进行全排列,再将结果与1组合。这样不断递归下去,直到所有元素都成为首位。 2. ...

    出、入栈所有排列的实现

    - 伪码算法:编写每一步操作的详细步骤,如当栈非空时,每次出栈一个元素,然后将剩余元素的所有排列作为新序列的起始项,重复此过程直到所有排列都被生成。 - 调用关系图:展示各模块间的调用关系,以便于理解和...

    求全排列的一个演示程序(C#编写)

    下面将详细介绍标题和描述中提到的四种算法,并提供相关的C#实现思路。 1. **字典序法** 字典序法是一种按照一定顺序生成全排列的方法。它通常从最小的排列开始,每次通过调整待排元素的位置来生成下一个排列。在...

Global site tag (gtag.js) - Google Analytics