递归排序算法原理_递归优化手段

递归排序算法原理_递归优化手段全排列表示把集合中元素的所有按照一定的顺序排列起来,使用P(n,n)=n!表示n个元素全排列的个数

考查递归 回溯

在这里插入图片描述
测试输入:

4
aacc

预期输出:

aacc
acac
acca
caac
caca
ccaa
6

思路:
全排列表示把集合中元素的所有按照一定的顺序排列起来,使用P(n, n) = n!表示n个元素全排列的个数。P(n, n)中的第一个n表示元素的个数,第二个n表示取多少个元素进行排列。

给定一个n个元素数组,其全排列的过程可以描述如下:
(1)任意取一个元素放在第一个位置,则有n种选择;
(2)再剩下的n-1个元素中再取一个元素放在第二个位置则有n-1种选择,此时可以看做对n-1个元素进行全排列;
(3)重复第二步,直到对最后一个元素进行全排列,即最后一个元素放在最后一个位置,全排列结束。

以数组{1,2,3}为例,其全排列的过程如下:
(1)1后面跟(2,3)的全排列;
(2)2后面跟(1,3)的全排列;
(3)3后面跟(1,2)的全排列。

在这里插入图片描述


去重的时候 是从前往后去重的
不然就不是样例的样子了 其实怎么去重都能得到个数

bool findsame(int idx,int m){ 
   
		for(int i = idx; i < m;i++)
			if(ch[m]==ch[i])  return 1;
		return 0;
}

过题代码:

#include<stdio.h>
#include<iostream>
using namespace std;
int n,cnt = 0;
char ch[550];
int a[550]; 
void sswap(int a,int b){ 
   
	char tmp = ch[a];
	ch[a] = ch[b];	ch[b] = tmp;
}
bool findsame(int idx,int m){ 
   
		for(int i = idx; i < m;i++)
			if(ch[m]==ch[i])  return 1;
		return 0;
}
//通过交换和挪动位置来实现排列 
void p(int len,int idx){ 
   
	if(idx==len-1){ 
   
		for(int i = 0; i < n;i++)
			printf("%c",ch[i]);
		printf("\n"); cnt ++;
	}else{ 
   
		for(int i = idx;i<len;i++){ 
   
		// cout<<idx<<" "<<i<<" "<<ch[i]<<" "<<findsame(idx,i)<<endl;
			if(findsame(idx,i)) continue;
			sswap(idx,i);
			p(len,idx+1);
			sswap(idx,i);
		}
	// cout<<"idx: "<<idx<<" "<<ch<<endl;
	}
	return;
}
int main(){ 
   
	scanf("%d\n",&n) ;
	for(int i = 0; i < n;i++)	
		scanf("%c",&ch[i]);
	p(n,0);
	printf("%d",cnt);
	return 0;
}

今天的文章递归排序算法原理_递归优化手段分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/83471.html

(0)
编程小号编程小号

相关推荐

发表回复

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