Seating arrangement program for foreign diplomats. What type of data structure to use.

I have to write a program that will create a seating arrangement for 10 diplomats from different countries.  The program has to take into account the languages spoken and the diplomatic relations between countries.  I am trying to figure out the best way to implement this program.
eric68Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

eric68Author Commented:
This is a description of the problem.
The table to be used for dinner is round, and seats 10 people. Your employer will be seated at the first position at the table. The other positions will be numbered clockwise from 2 to 10. The person seated to the left of your employer is in seat number 2, the person seated to the right of your employer is in seat number 10.

Persons seated next to each other must speak a common language. A person may speak to the person on the left in one common language, and speak to the person on the right in another language. The governments of the guests seated next to each other must have formally recognized each other.

The government of your employer has diplomatic relations with the governments of all of his guests. The government of a guest may or may not have diplomatic relations with the governments of all the other guests.

Two diplomats from the same country will have diplomatic relations with the same list of countries. A country will always have diplomatic relations with itself. Diplomats from the same country may or may not speak any languages in common.
0
robear7ntCommented:
Start out by thinking of the objects that would be involved here:

I would think you would have a Table object. What attributes would it have?
It might have a list of chairs usable as a seating arrangement.
It might need to check if two neighboring chairs had appropriate diplomats seating in them.

I would think you would have a Chair object. What attributes would it have?
It might be empty or it might have a single Diplomat assigned to it.
It might need to know which Chair is to it's left.
It might need to know which Chair is to it's right.

I would think you would have a Diplomat object. What attributes would it have?
It might have a list of languages that diplomat speaks.
It might have what government that diplomat is from.

I would think you would have a Government object. What attributes would it have?
It might have a list of friendly other governments.
It might have a list of it's diplomats.

Just some starting ideas, hope that gets you started.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ozoCommented:
I would probably approach this more abstractly,
looking to see if it could be transformed into a graph theory or set packing or block design or similar problem with a known soultion.
For somthing like this, I'd probably try to think about how I would want to solve it first, and then try to come up with a data structure that supports that method.
For example, if I wanted to start with a solution that did not satisfy all constraints
and apply transforms to try to get it to satisfy all constraints, I would want a data structure that made those transforms easy and detecting which constrants are satisfied easy.
I might also want ways of deciding which tranforms might be most efficacious
in reaching a solution, and I'd want a data structure that supported those ways.
0
Learn SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

sciuriwareCommented:
This is homework!

;JOOP!
0
rstaveleyCommented:
Is this why the world is in such a mess?
0
sciuriwareCommented:
No, it's only Easter.

;JOOP!
0
sciuriwareCommented:
Seriously: we, on EE,  are not allowed to solve school and course problems for students.

;JOOP!
0
rstaveleyCommented:
I was concerned that C++ programmers were arranging seating for diplomats. God forbid they'd have us controlling weapon systems too.

Erm... How does that rand() function work? ....
0
sciuriwareCommented:
Remember the failure of the Patriot's in the 1st Gulf War?  Software!
0
eric68Author Commented:
Thank you for all of the suggestions.  I am not looking for someone to solve my homework for me, I am just trying to get some suggestions on how to approach this problem (using graphs, sets, etc.), and I thought that the best people to ask would be programmers in the field since we are aloud to use any available resources.
0
Infinity08Commented:
>> I am just trying to get some suggestions on how to approach this problem

Did the posted comments help you get a better idea of what you'll need to do to implement this ?
Are you still unsure about certain parts ? (which ?)

It would maybe help if you would tell us how you think you'd do it. Explain with enough detail, so we can take a look at your approach, and give you tips on improving it if needed.
0
robear7ntCommented:
eric68,

This is an "interactive" process. The experts offer answers, suggestions, and comments to your question, then monitor the question waiting to hear feedback from you. Your feedback is vital to getting your question answered. Since this is a homework assignment, the experts can't solve it for you, but they will help guide you towards YOU being able to complete your assignment. The example in rules is: "You can teach them to count, but you can not tell them 2 + 2 = 4".

Robert
0
carchitectCommented:
Its a multidimensional matrix and kind of work assignment problem.

Try something like.

http://en.wikipedia.org/wiki/Quadratic_assignment_problem
0
ajibolaCommented:
how about using a graph algorithm. first of all the arrangement of the seating is needed to be established. Then the constraints. This is a Constraint Satisfaction Problem. http://en.wikipedia.org/wiki/Constraint_satisfaction_problem .Check out the examples there. You might need a heuristic like the value or 2 diplomats sitting close to each other, and far away. IF they have good relations then they should be closer there fore the heuristic value should be higher and if bad relations they should be apart, lower value. You should know what you want the heuristic to stand for, Closeness of diplomacy or seperation.
The goal of solving the problem is to make the most optimal selection at a point in time and when you get to a block back track. You could also apply forward checking for every decision made. This is when after a decision is made you take out all constraining posibilities, if you get to where the problem is unsolvable i.e some constrainst are not satisfied  you backtrack and take diff steps where necesary. you should do this from different starting points so as to reach a most feasible solution.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.