算法题目--寻找最长的到自身元素的映射集合

算法题目:给定一集合A[1...n]和一个从A 到其自身的映射f,寻找元素个数最多的一个子集S ⊆ A，并使得S 满足：

1．f 把S 映射到自身；

2．S 中没有两个元素映射到相同的元素

分析:

(1)首先介绍一下映射的概念

    定义：设A和B是两个非空集合，如果按照某种对应关系f，对于集合A中的任何一个元素，在集合B中都存在唯一的一个元素与之对应，那么，这样的对应（包括集合A，B，以及集合A到集合B的对应关系f）叫做集合A到集合B的映射(Mapping)，记作f：A→B。

    设f是由集合A到集合B的映射，如果x,y∈A,且x≠y时有f(x)≠f(y),则称f为由A到B的单射。

    函数为满射，当且仅当对任意b，存在a满足f(a) = b。

    既是单射又是满射的函数称为双射. 函数为双射当且仅当每个可能的像有且仅有一个变量与之对应。

(2)结合这个题目进行相应的考虑：

   对于集合A:有可能存在两个元素映射到相同元素的情况，但是注意一定不会有一个元素映射到两个元素的情况==>因为这不叫映射！！所以A中不可能存在两个相交的环。但是有可能存在环的尾巴

 

   对于所求的集合S的两点要求说明：它是A中环的集合，不存在环的尾吧，因为S 中没有两个元素映射到相同的元素。所以在S中E->A和D->A是不允许同时存在的。但是S中可以存在多个不相交的环的集合。

算法的基本的思想：这个是我们寝室的牛人Yang同学的成果，我拿过来学习一下，呵呵。

void main()

{

While (A不为空)

{

a=first(A); //取出A中第一个元素

while (a not in list)//是否形成了一个环，a在List中说明形成了一个环

{

if (a not in A) //a已经从A中删除，但是a已经不在list中,想想说明什么?

//这个是说明a曾经在list中存在过,也就是a已经是一个环的一部分

//这句话的目的是是为了去尾巴，当然这个尾巴是为了去后面加的尾

//巴，还有一种是为了去前面的尾巴

{

    clear(list);

    break;

}

        delete(a); //将a从A中删除

list.add(a);

a=f(a);

}

copyList(a,list,S); //将list中从a到结束的元素拷贝到S中,为什么从a开始就是为

//了去掉前面可能出现的尾巴，呵呵

clear(list);
    }

    output(S);

}

 

程序代码如下:

#pragma once
#include
#include
#include
#include

//===================================================//

数据结构A

class A
{
public:
 char * m_pData;
 size_t m_length;
public:
 A(int length = 6);
 ~A();
 A(const A &);
 A & operator=(const A &);
public:
 char GetFristData();//获得数组中的第一个数据
 void DeleteData(char a);//将数组中的元素值为a的元素删除
 bool IsEmpty();
 bool IsInA(char a);
};

A::A(int length)
{
 _ASSERT(length > 0);
 m_length = length;
 m_pData = new char[m_length + 1];
 memset(m_pData,'\0',m_length + 1);
}

A::~A()
{
 
}

A::A(const A & a)
{
 if (this != &a)
 {
  m_length = a.m_length;
  delete[] m_pData;
  m_pData = new char[m_length + 1];
  memcpy(m_pData,a.m_pData,m_length);
  m_pData[m_length] = '\0';
 }
 
}

A & A::operator=(const A & a)
{
 if (this != &a)
 {
  m_length = a.m_length;
  delete[] m_pData;
  m_pData = new char[m_length  + 1];
  memcpy(m_pData,a.m_pData,m_length);
  m_pData[m_length] = '\0';
 }
 return *this;
}

char A::GetFristData()
{
 if (m_length > 0)
 {
  return m_pData[0];
 }
}

bool A::IsEmpty()
{
 return m_length == 0;
}

bool A::IsInA(char a)
{
 for (int i = 0;i < m_length;i++)
 {
  if (m_pData[i] == a)
  {
   return true;
  }
 }
 return false;
}

void A::DeleteData(char a)
{
//删除A集合中的所有的元素值为a的单元

 std::vector deleteIndexVec;
 for (size_t i = 0;i < m_length;i++)
 {
  if (m_pData[i] == a)
  {
   deleteIndexVec.push_back(i);
  }
 }
 if (!deleteIndexVec.empty())
 {
  if (m_length - deleteIndexVec.size() != 0)
  {
   char * data = new char[m_length - deleteIndexVec.size() + 1];
   char * tmp = data;
   for (size_t i = 0;i < m_length;i++)
   {
    if (m_pData[i] != a)
    {
     memcpy(tmp,&m_pData[i],sizeof(char));
     tmp += sizeof(char);
    }
   }
   data[m_length - deleteIndexVec.size()] = '\0';
   delete [] m_pData;
   m_pData = NULL;
   m_length = m_length - deleteIndexVec.size();
   m_pData = data;
   tmp = NULL;
  }
  else
  {
   m_length = 0;
   delete [] m_pData;
   m_pData = NULL;
  }
 }
}

//=======================================================//

bool FindElement(char toBeFind,const std::vector & vec)
{
 bool bRet = false;
 std::vector::const_iterator It = std::find(vec.begin(),vec.end(),toBeFind);
 if (It == vec.end())
 {
  return bRet;//没找到
 }
 else
 {
  bRet = true;
  return bRet;
 }
}

char f(const char & a)//映射函数f
{
 
 switch (a)
 {
 case 'A':
  return 'B';
  break;
 case 'B':
  return 'C';
  break;
 case 'C':
  return 'D';
  break;
 case 'D':
  return 'C';
  break;
 }
}

//=====================================================//

void main()
{
 A a(4);
 a.m_pData[0] = 'A';
 a.m_pData[1] = 'B';
 a.m_pData[2] = 'C';
 a.m_pData[3] = 'D';
 std::vector list;
 list.clear();
 std::vector S;
 S.clear();
 char dataToProcess;
 while(!a.IsEmpty())
 {
  dataToProcess = a.GetFristData(); //取出A中第一个元素
  while (!FindElement(dataToProcess,list))//还没有形成环
  {
   if (!a.IsInA(dataToProcess)) //a已经从A中删除
   {
    list.clear();
    break;
   }
   
   a.DeleteData(dataToProcess); //将a从A中删除
   list.push_back(dataToProcess);
   dataToProcess = f(dataToProcess);
  }
  if (!list.empty())
  {
   std::vector::iterator listIt = std::find(list.begin(),list.end(),dataToProcess);
   std::copy(listIt,list.end(),std::back_inserter(S));
   list.clear();
  }
 }
 if (!S.empty())
 { 
  for (std::vector::const_iterator sIt = S.begin();sIt != S.end();sIt++)
  {
   std::cout<<*sIt<<",";
  }
  std::cout< }
 else
 {
  std::cout<<"不存在"< }
 getchar();
}

//---------------------------------------------------------------------------------------//

测试数据:

集合A:  ABCD

映射函数f

A->B B->C C->D D->C

程序结果：

S中集合的元素：CD