473,320 Members | 2,177 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

use gale shapley's algorithm to match companies and persons

nabh4u
62
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.

Expand|Select|Wrap|Line Numbers
  1. /----match.h--------------------------------------------------------------/
  2.  
  3. #include <iostream>
  4. #include<vector>
  5.  
  6. using namespace std;
  7.  
  8. /*------Declarations------*/
  9.  
  10. extern int n; // No. of companies.
  11. extern int m; // No. of persons.
  12. void read(); // Reads the input values from the user.
  13. void gsa(); // implementing gale shapley algorithm.
  14.  
  15. // class Data Structure for Company.
  16. class company
  17. {
  18. public:
  19.     int openPos; // "oi" No. of open positions in a company.
  20.     int perAccept; // "ai" No. of persons acceptable by company.
  21.     int cId; // Id's of companies.
  22.     vector <int> currentmatch; // vector to keep track of the current matches.
  23. };
  24.  
  25. // Class Data Structure for Person.
  26. class person
  27. {
  28. public:
  29.     int comAccept; // "ai" No. of companies acceptable by person.
  30.     int pId; // Vector containing Id's of persons.
  31.     vector <int> currentmatch; // vector to keep track of the current matches.
  32. };
  33.  
  34. /------------acme.cpp-------------------------------------------------------------/
  35.  
  36. # include"match.h"
  37.  
  38. using namespace std;
  39.  
  40. int main()
  41. {
  42.     cout<<"xxxxx\n";
  43.     read();// reads the input values from the user.
  44.     gsa(); // implements gale shapley algorithm.
  45.     return 0;
  46. }
  47.  
  48. /------------match.cpp-----------------------------------------------------------/
  49.  
  50. # include"match.h"
  51.  
  52. using namespace std;
  53.  
  54. int n; // No. of companies.
  55. int m; // No. of persons.
  56. int temp,temp1,temp2; // temporary variables to store data.
  57. company cpy; // an object of type company.
  58. vector <company> cmp; // a Vector of type company.
  59. vector <vector <int> > cPref; // Vector having the preference list for companies.
  60. vector <vector <int> > pPref; // Vector having the preference list for persons.
  61. person per; // an object of type person.
  62. vector <person> psn; // a Vector of type person.
  63. //vector <int>::iterator iter;
  64.  
  65.  
  66. // Reads the input values from the user.
  67. void read()
  68. {
  69.     cout<<"Enter the number of companies : ";
  70.     cin>>n;
  71.     cout<<"Enter the number of persons : ";
  72.     cin>>m;
  73.  
  74.     cPref.resize(n); // resize the vector.
  75.  
  76.     pPref.resize(m); // resize the vector.
  77.  
  78.     for(int i=0;i<n;i++)
  79.     {
  80.         cout<<"The company id :"<<i<<endl;
  81.         cpy.cId=i;
  82.         cout<<"Enter the number of open positions for company : ";
  83.         cin>>cpy.openPos;
  84.         cout<<"Enter the number of applicants acceptable : ";
  85.         cin>>cpy.perAccept;
  86.         cpy.currentmatch.resize(per.comAccept);
  87.         cmp.push_back(cpy);
  88.         cPref[i].resize(cpy.perAccept);
  89.  
  90.         for(int j=0;j<cpy.perAccept;j++)
  91.         {
  92.             cout<<"Enter the preference ";
  93.             cin>>temp; // this value goes in cPref.
  94.             cPref[i][j]=temp;
  95.         }
  96.     }
  97.     for(int i=0;i<cmp.size();i++)
  98.     {
  99.         cout<<cmp[i].cId<<" ";
  100.         cout<<cmp[i].openPos<<" ";
  101.         cout<<cmp[i].perAccept<<endl;
  102.     }
  103.  
  104.     for(int i=0;i<n;i++)
  105.     {
  106.         for(int j=0;j<cPref[i].size();j++)
  107.         {
  108.             cout<<cPref[i][j]<<" ";
  109.         }
  110.         cout<<endl;        
  111.     }
  112.  
  113.     for(int i=0;i<m;i++)
  114.     {
  115.         cout<<"Enter the person id :"<<i;
  116.         per.pId=i;
  117.         cout<<endl;
  118.     cout<<"Enter the number of companies acceptable for person : ";
  119.         cin>>per.comAccept;
  120.                                 per.currentmatch.resize(cpy.perAccept);
  121.         psn.push_back(per);
  122.         pPref[i].resize(per.comAccept);
  123.         for(int j=0;j<per.comAccept;j++)
  124.         {
  125.             cout<<"Enter the preference ";
  126.             cin>>temp1; // this value goes in cPref.
  127.             pPref[i][j]=temp1;
  128.         }
  129.     }
  130.     for(int i=0;i<psn.size();i++)
  131.     {
  132.         cout<<psn[i].pId<<" ";
  133.         cout<<psn[i].comAccept<<endl;
  134.     }
  135.     for(int i=0;i<m;i++)
  136.     {
  137.         for(int j=0;j<pPref[i].size();j++)
  138.         {
  139.             cout<<pPref[i][j]<<" ";
  140.         }
  141.         cout<<endl;        
  142.     }
  143. }
  144.  
  145. // Implements the Gale-Shapley algorithm.
  146. void gsa()
  147. {
  148.     // take the first company and check the no. of positions available
  149.     // if no positions are available then do nothing
  150.     // if positions are available then check the no. of acceptable.
  151.     // if acceptable is zero then do nothing
  152.     // otherwise check the preference for company to person
  153.     // if the person is free then the company hire that
  154.     // otherwise it should check its next preference and go on.
  155.     // once a company hires a person store the value of that person 
  156.     // in company's currentmatch and company value in persons currentmatch.
  157.  
  158.     for(int i=0;i<n;i++)
  159.     {
  160.         if(cmp[i].openPos!=0)
  161.         {
  162.             if(cmp[i].perAccept!=0)
  163.             {
  164.                if(cpy.currentmatch.size()!=0)
  165.                 {
  166.         for(int j=cmp[i].perAccept;j>0;j--)
  167.         {
  168.           temp2=cPref[i][j-1];
  169.                       for(int k=psn[i].comAccept;k>0;k--)                {
  170.                                   if(pPref[temp2][k-1]==i)
  171.                      {
  172.           cpy.currentmatch.push_back(pPref[temp2][k-1]);
  173.           per.currentmatch.push_back(cPref[i][j-1]);                              }
  174.         }
  175.                  }
  176.                }
  177.            }
  178.        }
  179.     }
  180.  
  181.     for(int i=0;i<cpy.currentmatch.size();i++)
  182.     {
  183.         cout<<cpy.currentmatch[i]<<endl;
  184.     }
  185.  
  186.     cout<<"akash";
  187.     for(int i=0;i<per.currentmatch.size();i++)
  188.     {
  189.         cout<<per.currentmatch[i]<<endl;
  190.     }
  191. }
  192.  
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.
Feb 1 '07 #1
3 4861
Banfa
9,065 Expert Mod 8TB
What output do you get?
Feb 2 '07 #2
Banfa
9,065 Expert Mod 8TB
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.
Feb 2 '07 #3
nabh4u
62
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.
Feb 2 '07 #4

Sign in to post your reply or Sign up for a free account.

Similar topics

16
by: cody | last post by:
I have to write an algorithm with must ensure that objects are put in buckets (which are always 4 in size). The objects have two properties: A and B. It is not allowed that in a bucket are objects...
13
by: M | last post by:
Hi, I've searched through the previous posts and there seems to be a few examples of search and replacing all occurrances of a string with another string. I would have thought that the code...
113
by: Bonj | last post by:
I was in need of an encryption algorithm to the following requirements: 1) Must be capable of encrypting strings to a byte array, and decyrpting back again to the same string 2) Must have the same...
1
by: hn.ft.pris | last post by:
"Forward maximum match" mean that there is a dictionary contains thousands of items which are single words. For example, "kid", "nice", "best"... And here get a string "kidnicebs", the forward...
4
by: mkppk | last post by:
MICR = The line of digits printed using magnetic ink at the bottom of a check. Does anyone know of a Python function that has been written to parse a line of MICR data? Or, some financial...
4
prometheuzz
by: prometheuzz | last post by:
Hello (Java) enthusiasts, In this article I’d like to tell you a little bit about graphs and how you can search a graph using the BFS (breadth first search) algorithm. I’ll address, and...
2
by: Bruce | last post by:
Hi I am trying to come up with an algorithm to solve the following problem. There are x components and y machines (y x) one machine can only run one component. Each component has 2 requirements...
6
Kelicula
by: Kelicula | last post by:
Why?: One commonly used algorithm is the binary search. If you don't already know it, you should read on. Very helpful. Saves much CPU. Reduces computations exponentially. When searching...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.