Algorithm - how to efficiently make sure elements from each array are distinct?

Question

I don't know how to write the title for this question. The existing title may not be precise.

Here is the problem:

I have m groups (arrays), say, 4 groups. Each group contains some numbers. What we wish is that each group gives one number out, and totally the resulting 4 numbers (each from one group) are distinct.

Now given these 4 groups, how can I make sure they fit to our wish?

For example,

A: 0, 2, 3

B: 0, 2

C: 2, 3

D: 1

The above 4 groups can fit to our wish. D gives 1, C gives 3, B gives 2, A give 0.

But if

A: 2

B: 2

C: 2, 3

D: 1

are bad. We can't let each group give an distinct number.

My idea is the most stupid way that I just do backtrack on all elements from all groups to get every combination of elements and see those elements from one combination are distinct or not.

Anyone has better idea?

tskuzzy · Accepted Answer · 2012-06-13 14:51:57Z

You can model this as a network flow problem and then use a fast algorithm in that problem domain (many of which are polynomial time) like Edmunds-Karp or push-relabel.

Create a source node and a sink node. Then create nodes for each "group" and for each distinct element. Connect each group node to the source and each element node to the sink. Finally connect group nodes with element nodes if the group as the element. All flow capacities should be 1.

This is best illustrated with an example. I'll use the first example you gave:

A: 0, 2, 3
B: 0, 2
C: 2, 3
D: 1

Will turn into the following flow network:

   A   0
  /     \
 /       \
S--B   1--T
 \       /|
  \     / |
   C   2 /
        /
       3

I couldn't draw the intermediate flows. But imagine that A flows to 0, 2, 3, and B flows to 0, 2, and C flows to 2, 3, and D flows to 1. All flows are unit capacity.

So first find the max-flow in this graph. The flows between the groups and elements will give you the bipartite matching that you want.

If there isn't a possible matching, then the max-flow will be less than the number of groups.

Mark · Accepted Answer · 2012-06-13 14:44:53Z

2

What you want is called a http://en.wikipedia.org/wiki/Bipartite_graph and you have a apply to it a http://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_cardinality_bipartite_matching. You can find the algorithm under this names :Maximum cardinality bipartite matching or maximum flow on a bipartite graph. Here is very good explained http://en.wikipedia.org/wiki/Maximum_matching and http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow , http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2 Hope that helped.

answered Jun 13, 2012 at 14:44

Mark

1,1009 silver badges18 bronze badges

Comments

clabacchio · Accepted Answer · 2012-06-13 14:49:18Z

0

One idea is to look for elements that are unique to all the groups, and use them for the group they belong to; this will narrow the list to only the groups with elements in common.
Another idea is to start from the group with the least elements (ideally one), set them to one of the values and iterate increasing the size (you can consider the size after removing the already used elements).

answered Jun 13, 2012 at 14:49

clabacchio

1,0672 gold badges18 silver badges29 bronze badges

Collectives™ on Stack Overflow

Algorithm - how to efficiently make sure elements from each array are distinct?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related