朱金灿
全排序算法就是列举一些字符的所有排列顺序的一种算法，比较典型的采用递归法。下面是一种简单的全排序算法。
void Swap(char* a, char* b)
{// 交换a和b
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void Perm(char list[], int k, int m)
{ //生成list [k：m ]的所有排列方式
int i;
if (k == m) {//输出一个排列方式
for (i = 0; i <= m; i++)
putchar(list[i]);
putchar('\n');
}
else // list[k：m ]有多个排列方式
// 递归地产生这些排列方式
for (i=k; i <= m; i++) {
Swap (&list[k], &list[i]);
Perm (list, k+1, m);
Swap (&list [k], &list [i]);
}
}
int main(int argc, char *argv[])
{
char s[6]="01234";
Perm(s,0,4);
return 0;
}
下面我简单地应用这个算法解决一道推理问题。该推理是这样的：
一天晚上，一对已婚夫妇，和他们的儿子女儿在家里发生了一起谋杀案，凶手、帮凶、被害人和目击者分别是家里的人。情况如下：
（1）目击者和那个帮凶不是同一性别
（2）年龄最大的和目击者不是同一性别
（3）年龄最轻的和被害人不是同一性别
（4）帮凶比受害者大
（5）父亲是年龄最长者
（6）凶手不是家中最年轻的成员
凶手、帮凶、被害人和目击者分别是谁？
算法的基本思路是：定义两个数组，一个数组表示家庭成员，另一个数组表示他们可能扮演的角色。当找出一种排列方式，然后一个数组对另一个数组赋值，如符合题目条件，则进行输出
代码如下：
#include <string.h>
#include <iostream.h>
struct Person
{
char szName[20];
bool Sex; // true 表示男，false表示女
int age; // 定义年龄
};
void Swap(char* a, char* b)
{// 交换a和b
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void
{
int i = 0;
if (k == m) {
for (i = 0; i <= m; i++)
{
Characters[i] = Familys[(list[i]-48)];
}
// 假如符合题目条件
if((Characters[1].Sex!=Characters[3].Sex) // 目击者和那个帮凶不是同一性别
&&(Familys[0].Sex!=Characters[3].Sex) //年龄最大的和目击者不是同一性别
&&(Familys[3].Sex!=Characters[2].Sex) // 年龄最轻的和被害人不是同一性别
&&(Characters[1].age>Characters[2].age)// 帮凶比受害者大
&&(Characters[0].age>20) // 凶手不是家中最年轻的成员
)
{
cout<<"murderer: "<<Characters[0].szName<<endl;
cout<<"accessary: "<<Characters[1].szName<<endl;
cout<<"be murdered: "<<Characters[2].szName<<endl;
cout<<"the age of be murdered: "<<Characters[2].age<<endl;
cout<<"eyewitness: "<<Characters[3].szName<<endl;
cout<<"the age of eyewitness: "<<Characters[3].age<<endl;
cout<<endl;
}
}
else
{
// 递归地产生这些排列方式
for (i=k; i <= m; i++)
{
Swap(&list[k], &list[i]);
Swap (&list [k], &list [i]);
}
}
}
int main(int argc, char* argv[])
{
// 定义一个家庭数组,Familys[0]为父亲,Familys[1]为母亲，Familys[2]为子女中年龄大的一个，Familys[3]为子女中年龄小的一个
Person Familys[4];
// 初始化数组成员，
strcpy(Familys[0].szName,"Father");
Familys[0].Sex = true;
Familys[0].age = 50;
strcpy(Familys[1].szName,"Mother");
Familys[1].Sex = false;
Familys[1].age = 40;
// 首先假设儿子的年龄比女儿要大
strcpy(Familys[2].szName,"Son");
Familys[2].Sex = true;
Familys[2].age = 30;
strcpy(Familys[3].szName,"Daughter");
Familys[3].Sex = false;
Familys[3].age = 20;
// 定义一个角色数组,Characters[0]为,Characters[1]为帮凶，Characters[2]为被害人，Characters[3]为目击者
Person Characters[4];
char s1[5]="0123";
Perm(s1,Familys,Characters,0,3);
char s2[5]="0123";
// 其次假设儿子的年龄比女儿要小
strcpy(Familys[2].szName,"Daughter");
strcpy(Familys[3].szName,"Son");
Familys[2].Sex = false;
Familys[3].Sex = true;
Perm(s2,Familys,Characters,0,3);
return 0;
}
其实在STL的next_permutation泛型算法已经实现了全排序，因此更为方便的做法是直接调用这个算法，代码如下：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
class Person
{
public:
Person();
Person(Person &Other);
bool CompareAge(Person &Other);
bool CompareAge(int nAge);
bool CompareSex(Person &Other);
void operator << (int nIndex);
void operator = (Person &Other);
void Initial(char *pszName,bool bSex,int nAge);
void ChangeAge(int NewAge);
private:
char m_szName[20];
bool m_Sex; // true 表示男，false表示女
int m_Age; // 定义年龄
};
Person::Person()
{
}
void Person::Initial(char *pszName,bool bSex,int nAge)
{
strcpy(m_szName,pszName);
m_Sex = bSex;
m_Age = nAge;
}
void Person::operator =(Person &Other)
{
strcpy(m_szName,Other.m_szName);
m_Sex = Other.m_Sex;
m_Age = Other.m_Age;
}
bool Person::CompareAge(Person &Other)
{
if(m_Age>Other.m_Age)
return true;
else return false;
}
bool Person::CompareAge(int nAge)
{
if(m_Age>nAge)
return true;
else return false;
}
bool Person::CompareSex(Person &Other)
{
if(m_Sex!=Other.m_Sex)
return true;
else return false;
}
void Person::ChangeAge(int NewAge)
{
m_Age = NewAge;
}
void Person::operator <<(int nIndex)
{
switch(nIndex)
{
case 0:
cout<<"murderer: "<<m_szName<<endl;
break;
case 1:
cout<<"accessary: "<<m_szName<<endl;
break;
case 2:
cout<<"be murdered: "<<m_szName<<endl;
cout<<"the age of be murdered: "<<m_Age<<endl;
break;
case 3:
cout<<"eyewitness: "<<m_szName<<endl;
cout<<"the age of eyewitness: "<<m_Age<<endl;
break;
default:
break;
}
}
void GetMurderer(Person Familys[])
{
vector<char> s1(4);
int i =0;
s1[0] = '0';
s1[1] = '1';
s1[2] = '2';
s1[3] = '3';
Person Characters[4];
for (i = 0; i <= 3; i++)
{
Characters[i] = Familys[(s1[i]-48)];
}
if(Characters[1].CompareSex(Characters[3])// 目击者和那个帮凶不是同一性别
&&(Familys[0].CompareSex(Characters[3]))//年龄最大的和目击者不是同一性别
&&(Familys[3].CompareSex(Characters[2])) // 年龄最轻的和被害人不是同一性别
&&(Characters[1].CompareAge(Characters[2]))// 帮凶比受害者大
&&(Characters[0].CompareAge(20)) // 凶手不是家中最年轻的成员
)
{
Characters[0]<<0;
Characters[1]<<1;
Characters[2]<<2;
Characters[3]<<3;
cout<<endl;
}
vector<char>::iterator start;
start = s1.begin();
vector<char>::iterator end;
end = s1.end();
while ( next_permutation(start,end))
{
for (i = 0; i <= 3; i++)
{
Characters[i] = Familys[(s1[i]-48)];
}
// 假如符合题目条件
if(Characters[1].CompareSex(Characters[3])// 目击者和那个帮凶不是同一性别
&&(Familys[0].CompareSex(Characters[3]))//年龄最大的和目击者不是同一性别
&&(Familys[3].CompareSex(Characters[2])) // 年龄最轻的和被害人不是同一性别
&&(Characters[1].CompareAge(Characters[2]))// 帮凶比受害者大
&&(Characters[0].CompareAge(20)) // 凶手不是家中最年轻的成员
)
{
Characters[0]<<0;
Characters[1]<<1;
Characters[2]<<2;
Characters[3]<<3;
cout<<endl;
}
}
}
int main(int argc, char* argv[])
{
// 定义一个家庭数组,Familys[0]为父亲,Familys[1]为母亲，Familys[2]为子女中年龄大的一个，Familys[3]为子女中年龄小的一个
Person Familys[4];
Familys[0].Initial("Father",true,50);
Familys[1].Initial("Mother",false,40);
Familys[2].Initial("Son",true,30);
Familys[3].Initial("Daughter",false,20);
GetMurderer(Familys);
// 交换儿子和女儿
Familys[2].ChangeAge(20);
Familys[3].ChangeAge(30);
Person tmpPerson;
tmpPerson = Familys[2];
Familys[2] = Familys[3];
Familys[3] = tmpPerson;
GetMurderer(Familys);
return 0;
}
编译环境：VC6.0 WinXp sp2
运行结果如下：
评论