[求助]一个像是排列又不是的算法。。。-付费问答-看雪-安全社区|安全招聘|kanxue.com

最新回复 (5)
icersg 雪币： 293 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 8 回帖 471 粉丝 0 关注私信	icersg 2 楼不就是排列组合吗？N个字符，结果是N的N次方种。可以用递归的方法，递归一次用一个循环确定一位，最后递归次数等于N的时候（或者从N开始，最后等于0的时候），就处理结果就行啦。 #include <string> static char set[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //象征性的写一下，其实没被用到 static char choose[27]; //存储选择的元素 static char combination[27]; //用于生成其中一个排列组合结果 static int length; //选择的元素的个数 //递归得到各种组合，n表示此轮递归被赋值的combination数组的index void getCombinations(int n) { if (n == length) { //当n等于选择的元素个数时，表示一个组合已经生成完毕，输出结果 printf("%s\n", combination); } else { //遍历choose所有的元素赋值给combination[n]，然后递归下一位 for (int i=0; i<length; i++) { combination[n] = choose; getCombinations(n+1); } } } int main() { //选择一些元素，比如'E','F','D' strcpy(choose, "EFD"); //获取选择的数量 length = strlen(choose); //开始递归 getCombinations(0); return 0; } 结果 EEE EEF EED EFE EFF EFD EDE EDF EDD FEE FEF FED FFE FFF FFD FDE FDF FDD DEE DEF DED DFE DFF DFD DDE DDF DDD Press any key to continue . . . 2009-2-4 22:59 0
yoohoow 雪币： 161 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 17 回帖 32 粉丝 0 关注私信	yoohoow 3 楼不好意思我没写清楚呢。~~！就给出字符集 char set[]="abcdefghijklmnopq";假设有N个字符集就从这些字符集取出k个(1<k<N); 组成不重复的字符集 abc,abd,abe,abf,abg.......................opq. 这样。。不知道怎么写哦。 2009-2-7 16:22 0
XSJS 雪币： 152 活跃值： (15) 能力值： ( LV2，RANK：10 ) 在线值：发帖 14 回帖 436 粉丝 1 关注私信	XSJS 4 楼哎呀，怎么最近那么多人问这个算法。。。 // NElementSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "windows.h" #include "stdlib.h" #include "atlstr.h" using namespace std; typedef struct{ bool IsVisit[26]; } my_type; void Visit(); char *element="abcdefghijklmnopqrstuvwxyz"; unsigned short n=0; class Status{ private: my_type Access; public: CString Loop; Status(){ ZeroMemory(&Access,sizeof(Access)); } my_type GetStatus(){ return Access; } void SetStatus(const my_type in){ Access=in; } } GloStatus; int main(){ cout<<"请输入元素个数:"; cin>>n; if(n>26){ cout<<"元素个数太多了!"<<endl; exit(0); } cout<<"将要排列的"<<n<<"个元素是:"; for(int x=0;x<n;x++){ cout<<element[x]; } cout<<endl; my_type Save; for(int x=0;x<n;x++){ ZeroMemory(&Save,sizeof(Save)); Save.IsVisit[x]=true; GloStatus.SetStatus(Save); GloStatus.Loop.Empty(); GloStatus.Loop.AppendChar(element[x]); Visit(); } return 0; } void Visit(){ my_type Save=GloStatus.GetStatus(),New=Save; bool IsEnd=true; for(unsigned short x=0;x<n;x++){ if(New.IsVisit[x]==false){ IsEnd=false; New.IsVisit[x]=true; GloStatus.Loop.AppendChar(element[x]); GloStatus.SetStatus(New); Visit(); GloStatus.Loop=GloStatus.Loop.Left((GloStatus.Loop.GetLength())-1); GloStatus.SetStatus(New=Save); } } if(IsEnd) cout<<GloStatus.Loop.GetString()<<endl; } 2009-2-7 16:35 0
icersg 雪币： 293 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 8 回帖 471 粉丝 0 关注私信	icersg 5 楼把2楼的那个代码稍微改一下就行了，结果是n=171615=4080个，太长了，就不贴了。感觉还是楼上的代码比较短，晚上吃玩饭研究一下，呵呵。 #include <string> static char set[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //象征性的写一下，其实没被用到 static char choose[27]; //存储选择的元素 static char combination[27]; //用于生成其中一个排列组合结果 static bool visit[26]; //如果已经选择了某个元素，就把相应的元素标为true static int chooseLength; //选择的元素的个数 static int combinationLength; //生成的组合的长度 //递归得到各种组合，n表示此轮递归被赋值的combination数组的index void getCombinations(int n) { if (n == combinationLength) { //当n等于生成的组合长度时，表示一个组合已经生成完毕，输出结果 printf("%s\n", combination); } else { //遍历choose所有的元素赋值给combination[n]，然后递归下一位 for (int i=0; i<chooseLength; i++) { //只挑选没被选过的元素 if (!visit) { visit = true; combination[n] = choose; getCombinations(n+1); visit = false; } } } } int main() { //初始化visit数组为false for (int i=0; i<26; i++) visit = false; //初始化combination为全0 for (int i=0; i<27; i++) visit = 0; //选择一些元素，比如abcdefghijklmnopq strcpy(choose, "abcdefghijklmnopq"); //获取选择的数量 chooseLength = strlen(choose); combinationLength = 3; //不知道到底你要多少，看你第一次描述是全排列，第二次的描述只有3个。。。 //开始递归 getCombinations(0); return 0; } 2009-2-7 17:19 0
yoohoow 雪币： 161 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 17 回帖 32 粉丝 0 关注私信	yoohoow 6 楼 ;好！！感谢所有TV 2009-2-9 13:05 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

icersg

雪币： 293

活跃值： (10)

能力值：

( LV2，RANK：10 )

在线值：

发帖

8

回帖

471

粉丝

0

关注

私信

icersg: 2 楼

不就是排列组合吗？N个字符，结果是N的N次方种。可以用递归的方法，递归一次用一个循环确定一位，最后递归次数等于N的时候（或者从N开始，最后等于0的时候），就处理结果就行啦。

#include <string>

static char set[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //象征性的写一下，其实没被用到
static char choose[27]; //存储选择的元素
static char combination[27]; //用于生成其中一个排列组合结果
static int length; //选择的元素的个数

//递归得到各种组合，n表示此轮递归被赋值的combination数组的index
void getCombinations(int n)
{
if (n == length)
{
//当n等于选择的元素个数时，表示一个组合已经生成完毕，输出结果
printf("%s\n", combination);
}
else
{
//遍历choose所有的元素赋值给combination[n]，然后递归下一位
for (int i=0; i<length; i++)
{
combination[n] = choose;
getCombinations(n+1);
}
}
}

int main()
{
//选择一些元素，比如'E','F','D'
strcpy(choose, "EFD");

//获取选择的数量
length = strlen(choose);

//开始递归
getCombinations(0);

return 0;
}

结果

EEE
EEF
EED
EFE
EFF
EFD
EDE
EDF
EDD
FEE
FEF
FED
FFE
FFF
FFD
FDE
FDF
FDD
DEE
DEF
DED
DFE
DFF
DFD
DDE
DDF
DDD
Press any key to continue . . .

2009-2-4 22:59

0

yoohoow

雪币： 161

活跃值： (10)

能力值：

( LV2，RANK：10 )

在线值：

发帖

17

回帖

32

粉丝

0

关注

私信

yoohoow: 3 楼

不好意思我没写清楚呢。~~！
就给出字符集
char set[]="abcdefghijklmnopq";假设有N个字符集
就从这些字符集取出k个(1<k<N);
组成不重复的字符集
abc,abd,abe,abf,abg.......................opq.
这样。。不知道怎么写哦。

2009-2-7 16:22

0

XSJS

雪币： 152

活跃值： (15)

能力值：

( LV2，RANK：10 )

在线值：

发帖

14

回帖

436

粉丝

1

关注

私信

XSJS: 4 楼

哎呀，怎么最近那么多人问这个算法。。。

// NElementSort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "windows.h"
#include "stdlib.h"
#include "atlstr.h"

using namespace std;

typedef struct{
	bool IsVisit[26];
} my_type;

void Visit();

char *element="abcdefghijklmnopqrstuvwxyz";
unsigned short n=0;

class Status{
private:
	my_type Access;

public:
	CString Loop;
	Status(){
		ZeroMemory(&Access,sizeof(Access));
	}
	my_type GetStatus(){
		return Access;
	}
	void SetStatus(const my_type in){
		Access=in;
	}
} GloStatus;

int main(){
	cout<<"请输入元素个数:";
	cin>>n;
	if(n>26){
		cout<<"元素个数太多了!"<<endl;
		exit(0);
	}
	cout<<"将要排列的"<<n<<"个元素是:";
	for(int x=0;x<n;x++){
		cout<<element[x];
	}
	cout<<endl;
	my_type Save;
	for(int x=0;x<n;x++){
		ZeroMemory(&Save,sizeof(Save));
		Save.IsVisit[x]=true;
		GloStatus.SetStatus(Save);
		GloStatus.Loop.Empty();
		GloStatus.Loop.AppendChar(element[x]);
		Visit();
	}
	return 0;
}

void Visit(){
	my_type Save=GloStatus.GetStatus(),New=Save;
	bool IsEnd=true;
	for(unsigned short x=0;x<n;x++){
		if(New.IsVisit[x]==false){
			IsEnd=false;
			New.IsVisit[x]=true;
			GloStatus.Loop.AppendChar(element[x]);
			GloStatus.SetStatus(New);
			Visit();
			GloStatus.Loop=GloStatus.Loop.Left((GloStatus.Loop.GetLength())-1);
			GloStatus.SetStatus(New=Save);
		}
	}
	if(IsEnd) cout<<GloStatus.Loop.GetString()<<endl;
}

2009-2-7 16:35

0

icersg

雪币： 293

活跃值： (10)

能力值：

( LV2，RANK：10 )

在线值：

发帖

8

回帖

471

粉丝

0

关注

私信

icersg: 5 楼

把2楼的那个代码稍微改一下就行了，结果是n=17*16*15=4080个，太长了，就不贴了。
感觉还是楼上的代码比较短，晚上吃玩饭研究一下，呵呵。

#include <string>

static char set[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //象征性的写一下，其实没被用到
static char choose[27]; //存储选择的元素
static char combination[27]; //用于生成其中一个排列组合结果
static bool visit[26]; //如果已经选择了某个元素，就把相应的元素标为true
static int chooseLength; //选择的元素的个数
static int combinationLength; //生成的组合的长度

//递归得到各种组合，n表示此轮递归被赋值的combination数组的index
void getCombinations(int n)
{
if (n == combinationLength)
{
//当n等于生成的组合长度时，表示一个组合已经生成完毕，输出结果
printf("%s\n", combination);
}
else
{
//遍历choose所有的元素赋值给combination[n]，然后递归下一位
for (int i=0; i<chooseLength; i++)
{
//只挑选没被选过的元素
if (!visit)
{
visit = true;
combination[n] = choose;
getCombinations(n+1);
visit = false;
}
}
}
}

int main()
{
//初始化visit数组为false
for (int i=0; i<26; i++)
visit = false;

//初始化combination为全0
for (int i=0; i<27; i++)
visit = 0;

//选择一些元素，比如abcdefghijklmnopq
strcpy(choose, "abcdefghijklmnopq");

//获取选择的数量
chooseLength = strlen(choose);
combinationLength = 3; //不知道到底你要多少，看你第一次描述是全排列，第二次的描述只有3个。。。

//开始递归
getCombinations(0);

return 0;
}