Geek Answers Handbook

How to arrange each according to preference?

This issue is from CodeEval 118 Problem

Your team is moving to a new office. To make them feel comfortable in the new place, you decide to let them choose the places they want. Each team member has provided you with a list of places that he / she will find acceptable. Your goal is to determine if everyone can be satisfied using these lists.

The seats in the new office are numbered from 1 to N. And the list of seat preferences that each team member provided you is unsorted.

Example input and output:

1:[1, 3, 2], 2:[1], 3:[4, 3], 4:[4, 3] --> Yes # possible 1:[1, 3, 2], 2:[1], 3:[1] --> No # not possible

How to solve it?

What have i tried? I believe that the solution will be recursive, and that’s what I came up with, but I don’t think I am breaking the problem down correctly into its smaller subtasks.

 def seat_team(num_seats, preferences, assigned): if len(preferences) == 1: for seat in range(len(preferences)): print preferences seat_wanted = preferences[0][1][seat] if not assigned[seat_wanted-1]: assigned[seat_wanted-1] = True return True, assigned return False, assigned else: for i in range(len(preferences)): current = preferences[i] for seat in current[1]: found, assigned = seat_team(num_seats, [preferences[i]], assigned) if not found: return False found, assigned = seat_team(num_seats, preferences[i+1:], assigned) if not found: return False return True num_seats = 4 preferences = [(1,[1,3,2]), (2,[1]), (3,[4,3]), (4,[4,3])] assigned = [False] * num_seats print seat_team(4, preferences, assigned)

Any ideas? I am sure that there is a common name for such problems and an algorithm for solving it, but I could not find similar problems (or solutions) on the Internet. Please share examples, if you know about them, I would really appreciate it.

+6
source share
2 answers

Just do it. Write a backtracking algorithm that assigns people to places and returns true / false if everyone can sit. Check it at small entrances to check its correctness. Then try on the big entrance. Optimize as needed.

Ideas for optimizations:

  • First appoint fussy people (who have a small amount of preference).
  • The marriage theorem in the hall provides a necessary and sufficient condition for a bipartisan correspondence to exist from people to places. All groups of people should be between them, as several places greater than or equal to their number. Obviously, the sufficient condition is too slow to check (there are 2 ** n subsets), but you can improve the reverse tracking algorithm by regularly checking the necessary condition for the remaining people and seats. This reduces the search space by firing branches earlier.

Tried this on a website. The delayed search algorithm scored 80. Scored 100 after the second optimization (regularly checking the status of the Hall)

My code. https://github.com/hickford/codeeval-solutions/blob/master/seat-your-team-members/seat-your-team-members.py

+3
source

This is the standard Bipartite Matching maximum issue.

The set S represents M vertices, each of which belongs to a member, and the set T represents N vertices, each for a place. There is an edge from S i to T j if the member i th wants j th place. This is a bipartite graph required. If the maximum match goes to M, then we have a different solution.

+5
source

More articles:


All Articles