DFA
A.First Edition
This is my first edition of DFA, however you can also regard it as a recursive edition of DFS. I am quite satisfied
with this edition as its clearance of logic and simplicity of algorithm and data structure are much more superior
than all previous editions.
I feel no happy, even disappointed for my DFS class! I didn't expect it had such a big bug after so many times
improvement! It shame me a lot! My logical for fixed level search is not clear, so I didn't realize that I need to
stop the program when it reaches the bottom by all means.
After all the assignment's simple recursive algorithm really attracts me a lot. As long as efficiency is not my
consideration, why don't I try recursive to simplify my program which is by now too complicated.
Also DFA's idea impressed me so much that I even admire myself since I am so lucky to use idea of DFA to solve
so many problems all by myself. Because I never realize that DFS=DFA until I listen to lecture of comp335.
A Depth-First-Search is by all means able to implement by recursive call as recursive call will always execute the
very bottom one where they stop. I am still afraid to write the complicated pointer manipulating code of DFS.
With recursive call, everything is OK except efficiency. But should I worry too much about efficiency?
I also save a lot of memory by remove those meaningless class objects list from my DFA class. In DFS user only
check the path he got, should he care about the sibling nodes? I guess not.
In DFA all choices are simply an element from Sigama, do we really need to care about the exact symbol? No, only
the index of symbol in Sigama matters. So, I only use a simple array to store the index choices chosen by user.
Why should I spend so much time to create a tree of objects of DFS? It is meaningless! OOP only want to combine
method with particular data structure, why should I create those useless nodes? So, now in memory there is simply
one object created, counted. That's it!
C.Further improvement
//file: DFA.h
#ifndef DFA_H
#define DFA_H
const int MaxSearchLevel= 100;
class DFA
{
protected:
int count;
int symbolCount;
int maxLevel;
char** symbolStr;
int level;//is count, level 0 stores nothing!
bool findAll;
bool countOnly;
int path[MaxSearchLevel];
void generate();
void update(int sonData);
void restore(int sonData);
bool touchDown();
virtual void output();
virtual void doUpdate(int sonData);
virtual void doRestore(int sonData);
//derived class must overload these functions!
virtual bool evaluate()=0;
virtual bool checkSymbol(int sonData)=0;
public:
//size of sigma must be defined, if user has his own label string, must
//pass the string array pointer here, otherwise only output default index
void setParam(int symbolSize, int maxSearchLevel=20, char** symbolString=NULL,
bool findAllChoices=false, bool onlyCount=false);
int getCount() const { return count;}
void search();//simply call generate()
DFA(int maxSearchLevel=100): count(0){;}
};
#endif
//file: DFA.cpp
#include <iostream>
#include "DFA.H"
using namespace std;
void DFA::setParam(int symbolSize, int maxSearchLevel, char** symbolString,
bool findAllChoices, bool onlyCount)
{
symbolCount = symbolSize;
maxLevel = maxSearchLevel;
symbolStr = symbolString;
findAll = findAllChoices;
countOnly = onlyCount;
level = 0;
}
void DFA::search()
{
generate();
}
void DFA::output()
{
cout<<"Solution No."<<count<<" is:\n";
if (symbolStr==NULL)
{
for (int i=0; i<level; i++)
{
cout<<path[i]<<'\t';
}
}
else
{
for (int i=0; i<level; i++)
{
cout<<symbolStr[path[i]]<<'\t';
}
}
cout<<endl;
}
void DFA::generate()
{
if (level!=0)
{
//check before test bottom
if (evaluate())
{
count++;
if (!countOnly)
{
output();
}
//only want one solution
if (!findAll)
{
return;
}
}
}
//always check to ensure!
if (touchDown())
{
return;
}
for (int i=0; i< symbolCount; i++)
{
if (checkSymbol(i))
{
update(i);
generate();
restore(i);
}
}
}
void DFA::update(int sonData)
{
level++;
path[level-1] = sonData;
doUpdate(sonData);
}
void DFA::restore(int sonData)
{
level--;
doRestore(sonData);
}
bool DFA::touchDown()
{
return level==maxLevel;
}
void DFA::doRestore(int sonData)
{
//leave for user's choices!
}
void DFA::doUpdate(int sonData)
{
//leave for user's choices!
}
//file: sequence.cpp
#include <iostream>
#include "DFA.H"
using namespace std;
int numbers[6] = {12, 13, 21, 23, 31, 32};
char* numberStr[6]={"12", "13", "21", "23", "31", "32"};
class Sequence: public DFA
{
protected:
virtual bool checkSymbol(int sonData);
virtual bool evaluate();
};
int main()
{
Sequence Seq;
Seq.setParam(6, 4, numberStr, true);
Seq.search();
Seq.setParam(6, 6, NULL, true, true);
Seq.search();
cout<<"For length 6 the total number of solution is:"<<Seq.getCount()<<endl;
return 0;
}
bool Sequence::evaluate()
{
return level== maxLevel;
}
bool Sequence::checkSymbol(int sonData)
{
bool result = false;
int current;
int selected = numbers[sonData];
int first;
if (level==0)
{
return selected ==12||selected == 13;
}
current = numbers[path[level-1]];
switch (current)
{
case 12:
result = selected==12||selected==13||selected==23||selected==21;
break;
case 13:
result = selected==13||selected==23||selected==21||selected==31;
break;
case 23:
result = selected==23||selected==21||selected==31||selected==32;
break;
case 21:
result = selected==21||selected==31||selected==32;
break;
case 31:
result = selected==31||selected==32;
break;
case 32:
result = selected==32;
break;
}
if (level+1<maxLevel)
{
return result;
}
else
{
first = numbers[path[0]];
switch (first)
{
case 12:
result = result &&(selected==21||selected==31||selected==32);
break;
case 13:
result = result &&(selected==31||selected==32);
break;
}
return result;
}
}
The result is like following:
Solution No.1 is: 12 12 12 21 Solution No.2 is: 12 12 13 21 Solution No.3 is: 12 12 13 31 Solution No.4 is: 12 12 21 21 Solution No.5 is: 12 12 21 31 Solution No.6 is: 12 12 21 32 Solution No.7 is: 12 12 23 21 Solution No.8 is: 12 12 23 31 Solution No.9 is: 12 12 23 32 Solution No.10 is: 12 13 13 21 Solution No.11 is: 12 13 13 31 Solution No.12 is: 12 13 21 21 Solution No.13 is: 12 13 21 31 Solution No.14 is: 12 13 21 32 Solution No.15 is: 12 13 23 21 Solution No.16 is: 12 13 23 31 Solution No.17 is: 12 13 23 32 Solution No.18 is: 12 13 31 31 Solution No.19 is: 12 13 31 32 Solution No.20 is: 12 21 21 21 Solution No.21 is: 12 21 21 31 Solution No.22 is: 12 21 21 32 Solution No.23 is: 12 21 31 31 Solution No.24 is: 12 21 31 32 Solution No.25 is: 12 21 32 32 Solution No.26 is: 12 23 21 21 Solution No.27 is: 12 23 21 31 Solution No.28 is: 12 23 21 32 Solution No.29 is: 12 23 23 21 Solution No.30 is: 12 23 23 31 Solution No.31 is: 12 23 23 32 Solution No.32 is: 12 23 31 31 Solution No.33 is: 12 23 31 32 Solution No.34 is: 12 23 32 32 Solution No.35 is: 13 13 13 31 Solution No.36 is: 13 13 21 31 Solution No.37 is: 13 13 21 32 Solution No.38 is: 13 13 23 31 Solution No.39 is: 13 13 23 32 Solution No.40 is: 13 13 31 31 Solution No.41 is: 13 13 31 32 Solution No.42 is: 13 21 21 31 Solution No.43 is: 13 21 21 32 Solution No.44 is: 13 21 31 31 Solution No.45 is: 13 21 31 32 Solution No.46 is: 13 21 32 32 Solution No.47 is: 13 23 21 31 Solution No.48 is: 13 23 21 32 Solution No.49 is: 13 23 23 31 Solution No.50 is: 13 23 23 32 Solution No.51 is: 13 23 31 31 Solution No.52 is: 13 23 31 32 Solution No.53 is: 13 23 32 32 Solution No.54 is: 13 31 31 31 Solution No.55 is: 13 31 31 32 Solution No.56 is: 13 31 32 32
For length 6 the total number of solution is:357
Press any key to continue