How to create distinct set from other sets?

While solving the problems on Techgig.com, I got struck with one of the problems. The problem is like this:

A company organizes two trips for their employees in a year. They want to know whether all the employees can be sent on the trip or not. The condition is that no employee can go on both the trips. Also to determine which employees can go together the constraint is that the employees who have worked together in past won’t be in the same group. Examples of the problem:

Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and the other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past.

Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no possible way to have two trips satisfying the company rule and accommodating all the employees.

Can anyone tell me how to proceed on this problem?

Here is a hint. I see that you can solve this in 2 steps. as follows:

Part 1 – Identify Eligible Pairs

First, we could identify, according to requirements rules, pairs of employees who could travel together on one trip using the matrix below based on your stated case: {(1,2),(2,3),(3,4)}

Cells with x (as well as the diagonal cells) represent instances where 2 employees can travel together because they worked together.

Also, it is implied that travelTogether(i,j)=travelTogether(j,i) (Blue cells are deduced from input) and that

travelTogether(i,i)=”x” (meaning No, or false).

non-marked cells indicate ‘yes’ or true, that is the pair travelTogether(i,j) can travel together on the same trip. For example, employee 1 can travel with 3 and/or 4. However, Employee 3 can only travel with 1.

Part 2. Identify Candidates per Trip

-You have 2 trips.

-You have pairs that must travel together (or not travel at all) such as Employee 3.

-You don’t have no maximum capacity per trip.

For each employee determine number of available travel mates.

Sorting the employees on that number of available travel mates we get:

So Each of the employees 2 and 3 can choose 1 trip mate. Starting by the 2 (arbitrary selection), you place 2 with its only possible mate 4. This leaves 3 and 1 to travel together. You could then have 1 trip to include (2,4) and another for (3,1).

You could to write a standard complete search to solve the problem in a primitive but reliable way. Simply assign any employee (arbitrarily) to trip 1, then assign the next employee to either 1 or 2, etc., back-tracking whenever you can’t place the next employee on either trip, and terminating if all employees are assigned.

The more interesting question is whether the search can be made more efficient. In this case, since past co-workers cannot travel together, you can immediately assign all co-workers of anyone you place on trip 1 to trip 2 – and then you can assign all of their co-workers to trip 1, for the same reason, and so on until constraint 2 doesn’t give you any new information. If you encounter any constraint violation during this process, the problem is unsolvable. This will not find a solution faster than the naive solution, but it can prove the absence of a solution much faster, since you don’t have to backtrack your way through the entire solution space. An additional optimization could be to place the employees with the most co-workers first, since this excludes more parts of the solution space than placing a solitary worker.

This problem can be reduced to a bipartite graph problem.

Bipartite Graphs

If the vertices of a graph can be divided into two groups, such that

there exists no edge between any two vertices in the same group
(for every node, there is an edge that connects it to a vertex of the other group)

Abstracting away

We notice that

the people will be partitioned into two groups
only people in different groups share some kind of relationship with each other

Knowing that an (undirected) graph is simply a visualization of a (symmetric) relation, and a partitioning of its objects (i.e. persons) into two groups, and all edges connect vertices from different groups, we can see that this in fact qualifies as a bipartite graph, if such a partitioning is indeed possible.

We conclude that we must only determine, if it is a (relaxed) bipartite graph. Relaxed, because in the proper definition, every vertex must have at least one edge, but the problem does not specify whether that is the case. This is why (2) is in parentheses.

Detecting a bipartite graph

This can be done with either a breadth-first-search (BFS) of a depth-first-search (DFS) algorithm.

We can place the first vertex into group #1. (It does not matter which)
Having done that, it is clear that all its neighbors must be placed in group #2, since neighbors are those, that have have worked with the first person. Thus, they may not be in the group #1.
Similarly, we place all the neighbors’ neighbors into group #1
Continuing the same way, we assign the nodes to the two different groups.

However, in case a bipartite graph cannot be formed, we have to stumble across a node when trying to assign it to group X, that was already assigned to a group, but not group X. In that case, it is impossible to form two groups of employees where nobody has worked with each other before.

DFS/BFS modification

Upon discovering a neighboring node, we place it in the opposite group of the currently active node, if it has not been assigned one yet.

In case it has already been assigned to the same node, we know it’s impossible to form a bipartite graph.

Otherwise, it has already placed into a group conforming rule (1) of a bipartite graph.

Dealing with rule (2)

In case rule (2) is not in effect, i.e. the graph has more than one connected components, DFS/BFS will terminate before having assigned all nodes to a group.

In that case, the algorithm is simply run again on a yet unassigned node, until no such nodes are left.

Getting all solutions

In case rule(2) is not in effect, there exist more than just two solutions. For a graph with c connected components, (i.e. the DFS/BFS algorithm was run c times), there are 2^c solutions.

For that, we need to differentiate between the two groups created by each invocation of the BFS/DFS algorithm: g_c,1 and g_c,2 for run c.

After having run the algorithm c times, we distribute the c pairs to two groups, in which the employees are being separated, freely.

Filed under: softwareengineering - @ 07:30

Thẻ: algorithms

Thiết kế website giá rẻ

Danh mục