Choose n distinct number from n set

Блог пользователя Frez

Автор Frez, история, 11 лет назад, По-английски

Suppose we have n set of numbers . we want to choose a number from each set that they were distinct . how we can do it efficiently ?

A -> 1 <= n <= 20 , 1 <= |s| <= 100 , 1 <= numbers <= 10^9

B -> 1 <= n <= 10^5 , 1 <= |s| <= 10^5 , 1 <= numbers <= 10^9

C -> In General ?

thanks in advance.

set, choose, discrete

Frez
11 лет назад
5

Комментарии (5)

Написать комментарий?

Frez

11 лет назад, скрыть # |

Auto comment: topic has been updated by Frez (previous revision, new revision, compare).

→ Ответить

TimonKnigge

11 лет назад, скрыть # |

← Rev. 23 →

+17

Denote the n sets as (A_i)_i = 1..n, then let $\text{[math]}$ . Now consider a bipartite graph with a vertex for each set on the left side, a vertex on the right set for each element $\text{[math]}$ , and an edge from the vertex representing set A_i to the vertex representing the element x if and only if $\text{[math]}$ . Clearly any maximum bipartite matching induces a selection of elements from the sets such that each element is distinct (prove this yourself).

In other words, the problem can certainly be solve in polynomial time. However, the complexity isn't great. The number of vertices is n + |S| (recall that S is the set of distinct elements), and the number of edges is $\text{[math]}$ . Hopcroft-Karp gives an $\text{[math]}$ algorithm. (Note: using a appropriate datastructures (maps etc) this reduction takes $\text{[math]}$ time, it is important that the complexity of the new problem supersedes the complexity of the reduction).

However, the reduction works the other way around. Given a bipartite graph, denote the left side as V₁ and the right side as V₂. For $\text{[math]}$ , let $\text{[math]}$ . If we can select a distinct element from each set, this clearly induces a complete bipartite matching. Note that this reduction takes O(V₁ + V₂ + E) time, less than the best known bound on bipartite matching.

In other words, this problem is equivalent to deciding whether a bipartite graph has a maximal matching.

EDIT: Hopcroft-Karp is $\text{[math]}$ , not $\text{[math]}$ .

→ Ответить

Frez

11 лет назад, скрыть # ^ |

← Rev. 2 →

THANKS:) really awesome! This was hard for me to understand but I got it finally.

related problem is here. I hope I can solve it now :D

→ Ответить

TimonKnigge

11 лет назад, скрыть # ^ |

That problem is a bit different from the one you mentioned above (or maybe I misinterpreted it). But you can also solve it using bipartite matching.

→ Ответить

TimonKnigge

11 лет назад, скрыть # ^ |

I just tried the problem and (as expected) it worked. Of course I would recommend first trying it yourself, but if you can't figure it out, here is my solution. All relevant code is in the main (the rest is just generic max flow code), I added some comments to make everything clear.

→ Ответить