Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Lets say I have four group

A [ 0, 4, 9] B [ 2, 6, 11] C [ 3, 8, 13] D [ 7, 12 ]

Now I need a number from each group(i.e a new group) E [num in A,num in B, num in C, num in D], such that the difference between the maximum num in E and minimum num in E should be possible lowest.What type of problem is this ? which graph algorithm will be better to solve this kind of problem ? Thanks in advance.

share|improve this question
2  
Why do you think this has anything to do with graphs? –  Chris Eagle Aug 25 '12 at 17:03
    
@ChrisEagle shortest path that travels only one node in every group. P.S: I'm asking here for help only because I'm not sure about it. –  user1624525 Aug 25 '12 at 17:10
    
What is the type of each element ? is it an integer ? –  Belgi Aug 25 '12 at 17:37
    
I guess if max num in E = min num in E, the problem reduces down to a combinatorial search problem that has non-polynomial complexity. –  tatterdemalion Aug 25 '12 at 17:55
    
@Joe - from what I understand you have to find an option to get the minimum, not all options –  Belgi Aug 25 '12 at 18:13
add comment

1 Answer

up vote 2 down vote accepted

I can't think of any reasonable way to represent this problem using graphs.

I suggest the following to deal with your problem:

1) keep the elements of each groups sorted .

denote $n$ as the total number of elements ($n=|A|+...+|D|)$, for each $M\in\{A,B,C,D\}$ denote$U_{M}$ as the union of the other groups with higher alphabetical order (for example $U_{B}=C\cup D)$.

2) since we have to choose one element from each group we have to choose one from $M$, for every element in $M$ find an element in$U_{M}$ s.t the difference is minimal (since the elements are sorted you can do this in $log(|U|)$ using binary search).

save this minimum in a variable and update it when you find a new minimum (also save the elements that gave you the minimum and the groups they came from so you can know what elements in what groups give this minimum)

At the end of this procedure you will know what two elements in which groups give you your minimum, of course you can take the other two elements for $E$ in an arbitrary way without it affecting the minimum.

The time complexity is $O(nlog(n))$ since for every $M$ it holds that $|M|\leq n$ and$|U_{M}|\leq n$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.