有重复元素的排列问题

[效云 李]

网上没找到好的原题，题目见算法实现题2-8

[效云 李]

// 递归分治-有重复元素的排列问题.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int n=0;
string s;
ifstream finput;
finput.open("input.txt");
finput>>s;
n=s.length();

void perm(string&,int,int);
perm(s,0,n-1);
system("pause");
return 0;
}

void perm(string& s,int k,int m)
{
void swap(int,int,string&);
int ok(string,int,int);
if(k==m)
{
for(int i=0;i<=m;++i) cout<<s[i];
cout<<endl;
}
else
for(int i=k;i<=m;++i)
{
if(ok(s,k,i))
{
swap(k,i,s);
perm(s,k+1,m);
swap(k,i,s);
}

}
}

void swap(int i,int j,string& s)
{
char temp=s[i];
s[i]=s[j];
s[j]=temp;
}

int ok(string s,int k,int i)
{ //关键是这个函数，通过查找在i前面，有没有相同的字符，因为若有，即使交换了，然后再递归下去，这种情况在前面已经出现过，
//产生重复的原因，是因为，有两个字符相同，这个函数可以看成是，从头往尾递归，一开始，我可以不管，那么我来阻止你出现重复
//的可能性，重复就是因为交换相同元素照成的，所以，这个函数，也可以实现，成功的组织，不多也不少
if(i>k)for(int t=k;t<i;++t) if(s[t]==s[i])return 0;
return 1;
}

On 4月21日, 下午5时14分, 效云 李 <lixiaoyun...@gmail.com> wrote:
> 网上没找到好的原题，题目见算法实现题2-8

[zhong nanhai]

你做的太快了，也。

[李效云]

这个题目，怎么说呢，除了那最后一个函数，死活都想不起来，
其他的还是比较正常吧，那个函数一看提示，觉的，确实比较简洁有思想啊

2009/4/21 zhong nanhai <higerin...@gmail.com>