please help me as i have a very short deadline to submit this program.
Expand|Select|Wrap|Line Numbers
- /----match.h--------------------------------------------------------------/
- #include <iostream>
- #include<vector>
- using namespace std;
- /*------Declarations------*/
- extern int n; // No. of companies.
- extern int m; // No. of persons.
- void read(); // Reads the input values from the user.
- void gsa(); // implementing gale shapley algorithm.
- // class Data Structure for Company.
- class company
- {
- public:
- int openPos; // "oi" No. of open positions in a company.
- int perAccept; // "ai" No. of persons acceptable by company.
- int cId; // Id's of companies.
- vector <int> currentmatch; // vector to keep track of the current matches.
- };
- // Class Data Structure for Person.
- class person
- {
- public:
- int comAccept; // "ai" No. of companies acceptable by person.
- int pId; // Vector containing Id's of persons.
- vector <int> currentmatch; // vector to keep track of the current matches.
- };
- /------------acme.cpp-------------------------------------------------------------/
- # include"match.h"
- using namespace std;
- int main()
- {
- cout<<"xxxxx\n";
- read();// reads the input values from the user.
- gsa(); // implements gale shapley algorithm.
- return 0;
- }
- /------------match.cpp-----------------------------------------------------------/
- # include"match.h"
- using namespace std;
- int n; // No. of companies.
- int m; // No. of persons.
- int temp,temp1,temp2; // temporary variables to store data.
- company cpy; // an object of type company.
- vector <company> cmp; // a Vector of type company.
- vector <vector <int> > cPref; // Vector having the preference list for companies.
- vector <vector <int> > pPref; // Vector having the preference list for persons.
- person per; // an object of type person.
- vector <person> psn; // a Vector of type person.
- //vector <int>::iterator iter;
- // Reads the input values from the user.
- void read()
- {
- cout<<"Enter the number of companies : ";
- cin>>n;
- cout<<"Enter the number of persons : ";
- cin>>m;
- cPref.resize(n); // resize the vector.
- pPref.resize(m); // resize the vector.
- for(int i=0;i<n;i++)
- {
- cout<<"The company id :"<<i<<endl;
- cpy.cId=i;
- cout<<"Enter the number of open positions for company : ";
- cin>>cpy.openPos;
- cout<<"Enter the number of applicants acceptable : ";
- cin>>cpy.perAccept;
- cpy.currentmatch.resize(per.comAccept);
- cmp.push_back(cpy);
- cPref[i].resize(cpy.perAccept);
- for(int j=0;j<cpy.perAccept;j++)
- {
- cout<<"Enter the preference ";
- cin>>temp; // this value goes in cPref.
- cPref[i][j]=temp;
- }
- }
- for(int i=0;i<cmp.size();i++)
- {
- cout<<cmp[i].cId<<" ";
- cout<<cmp[i].openPos<<" ";
- cout<<cmp[i].perAccept<<endl;
- }
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<cPref[i].size();j++)
- {
- cout<<cPref[i][j]<<" ";
- }
- cout<<endl;
- }
- for(int i=0;i<m;i++)
- {
- cout<<"Enter the person id :"<<i;
- per.pId=i;
- cout<<endl;
- cout<<"Enter the number of companies acceptable for person : ";
- cin>>per.comAccept;
- per.currentmatch.resize(cpy.perAccept);
- psn.push_back(per);
- pPref[i].resize(per.comAccept);
- for(int j=0;j<per.comAccept;j++)
- {
- cout<<"Enter the preference ";
- cin>>temp1; // this value goes in cPref.
- pPref[i][j]=temp1;
- }
- }
- for(int i=0;i<psn.size();i++)
- {
- cout<<psn[i].pId<<" ";
- cout<<psn[i].comAccept<<endl;
- }
- for(int i=0;i<m;i++)
- {
- for(int j=0;j<pPref[i].size();j++)
- {
- cout<<pPref[i][j]<<" ";
- }
- cout<<endl;
- }
- }
- // Implements the Gale-Shapley algorithm.
- void gsa()
- {
- // take the first company and check the no. of positions available
- // if no positions are available then do nothing
- // if positions are available then check the no. of acceptable.
- // if acceptable is zero then do nothing
- // otherwise check the preference for company to person
- // if the person is free then the company hire that
- // otherwise it should check its next preference and go on.
- // once a company hires a person store the value of that person
- // in company's currentmatch and company value in persons currentmatch.
- for(int i=0;i<n;i++)
- {
- if(cmp[i].openPos!=0)
- {
- if(cmp[i].perAccept!=0)
- {
- if(cpy.currentmatch.size()!=0)
- {
- for(int j=cmp[i].perAccept;j>0;j--)
- {
- temp2=cPref[i][j-1];
- for(int k=psn[i].comAccept;k>0;k--) {
- if(pPref[temp2][k-1]==i)
- {
- cpy.currentmatch.push_back(pPref[temp2][k-1]);
- per.currentmatch.push_back(cPref[i][j-1]); }
- }
- }
- }
- }
- }
- }
- for(int i=0;i<cpy.currentmatch.size();i++)
- {
- cout<<cpy.currentmatch[i]<<endl;
- }
- cout<<"akash";
- for(int i=0;i<per.currentmatch.size();i++)
- {
- cout<<per.currentmatch[i]<<endl;
- }
- }
The preference list goes like thisan example)
company(has person ids from least preferable to most preferable)
4 3 2 1
3 1 2 4
3 2 4 1
person(has company ids from least preferable to most preferable)
3 2 1
3 1
3 1 2
1 2 3
with these preference lists i should get an output like:
persons ids companyids
4 3
3 2
2 1
1 1
in this way i should get that company 1 hires person 1 and 2. and so on.