use gale shapley's algorithm to match companies and persons

[nabh4u]

i have a program where i have to use gale shapley's algorithm to match companies and persons. i create preference lists for both companies and persons. i am almost done but i am not getting the output. i should get the output with the persons who were hired and the companies who hire them.
please help me as i have a very short deadline to submit this program.

/----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;
    }
}
 

A company can hire more than 1 employee based on the number of openings and the number of persons acceptable.
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.

[Banfa]

What output do you get?

[Banfa]

Also perhaps you had better post the detail of this algorithm you are trying to implement, or a link to a page with the detail.

[nabh4u]

the Program details are like this:

General description
The Acme Employment Agency has a proprietary test which it gives to each company seeking workers and another test which it gives to each person seeking employment. These tests allow them to construct an accurate preference list for each company and each person. Using these lists, they make hiring recommendations for each company. They are in competition with the other agencies which produce similar lists of hiring recommendations . To insure customer satisfaction, they guarantee that no company will prefer to hire any employee who would prefer to work for that company in preference to the one that they recommend. They also guarantee that the none of their competitors will produce a similar list which any company would prefer to theirs. Your task is to create the list of hiring recommendations .
Specifics for this assignment
You will read in the preference lists for each company and each employee and print out the hiring recommendations and the total number of recommendations made. For simplicity, all input is from standard input, and all output is to standard output.
Input format
You should print a single prompt, which includes your name and ends with a newline character. The program will then read an integer, n, which is the number of companies, and an integer m, which is the number of persons.
It will then read the preference lists for the companies, from company 0 to company n-1. For each company, it will read an integer, oi, which is the number of open positions that the company wishes to fill, and an integer ai, which is the number of applicants which the company finds acceptable. ai may be 0, in which case company i would rather leave the positions unfilled than hire any of the available applicants. It will then read ai integers, pij, which comprise the preference list of company i. 0 £ pij < m. Each pij is the id of a person, so each preference list is a list of the persons the company is willing to hire, from least desirable to most desirable. After all the preference lists for the companies are read, the program will read the preference lists for the potential employees. For each person, it will read an integer ai, which is the number of companies the person finds acceptable. ai may be 0, in which case person i person i would rather remain unemployed than work for any of the companies. It will then read ai integers, pij, which comprise the preference list of person i. 0 £ pij < n. Each pij is the id of a company, so each preference list is a list of the companies the person is willing to work for, from least desirable to most desirable.
Note that the integers are in free format, which means that they may be divided into any number of lines. Do not attempt to parse each line, as that is unnecessary.
Internal representation
You should choose an efficient internal representation. Choosing an inefficient internal representation is an error.
Output format
The companies' hiring lists should be printed in order of decreasing company ID. For each company, you should print one line. This line should contain the following integers. First print the number of employees this company will hire. Then print the IDs of these employees. The employee IDs should be printed in order of increasing ID. Each pair of integers should be separated by exactly one space.
After all the companies' hiring lists have been printed, print a blank line and then a line containing one integer, the number of companies which hire at least one employee. Do not print any spaces on either of these lines.
Then print the employees' hiring lists, in order of decreasing person ID. For each person, you should print one line. This line should contain the ID of the company. If the person is not hired, this integer should be -1. Do not print any spaces on these lines.
After all the employees' hiring lists have been printed, print a line containing one integer, the number of persons who were hired. Do not print any spaces on this line.
Then you should print a line containing your name. Be sure to print a newline character at the end of this line.

i was getting an output with zeros first and then the values which i wanted an then repeated values.

Also perhaps you had better post the detail of this algorithm you are trying to implement, or a link to a page with the detail.