problem to generate all possible combinations in two sets
Hello All,
I have a question which is troubling me quite a bit.
I have two sets
A={1,2,3}
B={4,5,6}
Answer needed
(4,1),(4,2),(4,3).
(5,1),(5,2),(5,3)
(6,1),(6,2),(6,3)
Mapping can be done only when the second set element is greater than the first set element.
A={4,5,6}
B={1,2,3}
Mapping cannot be done.In this case.
Answer
Mapping not possible.
The sets will be as large as 100 or more.
I need to figure out how to do it efficiently.It should be fast and should take up least memory.I need to store these sets later.I would be glad if someone could help me in this.
Thanks.
Regards.
Nitin.p
How many times are you going to post this thread? If you want people to answer it again and again, how about saying precisely how their solutions fail to work? For example, what's the problem with the solution I gave you earlier?
And yet another solution to this problem.
//import java.util.*;
public static Map findPairs(Set a, Set b) {
Map lhm = new LinkedHashMap();
Iterator itA = a.iterator();
while(itA.hasNext()) {
Iterator itB = b.iterator();
while(itB.hasNext()) {
Integer intA = (Integer) itA.next();
Integer intB = (Integer) itB.next();
if(intA.compareTo(intB)>0) lhm.put(intA,intB);
}
}
return lhm;
}
matfud
Hi there,Thanks.I thought the forums was meant with people with adequate patience.You could have ignored it if you felt it was being posted again and again.I wont post it agian.Thanks.Regards.N.P
Hello there,Thanks a lot.Regards.NP
Hi there,I thought this part of the actually code i was working on caused the delay but it realized this wasnt the case after i posted it.Thanks.Regards.Nitin.P
> Thanks.I thought the forums was meant with people with> adequate patience.A lot of people think a lot of things. I think you are a tool for posting this response. I also think you should put at least one space after the end of a sentence.
A different version that may be faster then the previous one I posted.
(depends on the difference in cost between creating a Set and creating
a SortedSet)
A similar thing can be done with sorted arrays.(which would probably be
faster still)
//import java.util.*;
public static Map findPairs(Set a, SortedSet b) {
Map lhm = new LinkedHashMap();
Iterator itA = a.iterator();
while(itA.hasNext()) {
Object objA = itA.next();
SortedSet tail = b.tailSet(objA);
Iterator itB = tail.iterator();
while(itB.hasNext()) {
lhm.put(objA,itB.next());
}
}
return lhm;
}
matfud
Hi Dubwai,You are a bigger fool who wasted your time telling me that I was a fool.I am a bigger fool than you to tell you this.So you are a small fool so dont show off in front of a bigger fool.Bye bye.Regards.NP
Hi mat,Thanks a lot.Regards.NP.
> You are a bigger fool who wasted your time telling me> that I was a fool.I am a bigger fool than you to tell> you this.So you are a small fool so dont show off in> front of a bigger fool.When did I say you are a fool? I said you are a tool.
Hello Yat,My humble apologies to you.I found your solution.The obvious answer is to sort one (as a List, obviously) and then run two iterations. Since that's asymptotically optimal, I'd run with it. Thanks.Regards.NP(Kicks Himself)
Hello Dubwai,My humble apologies to you.I shall post it properly.Thanks.Regards.NP
Hello Yat,
I needed the solution for this.
Hello All,
This is the problem I am stuck with right now.
I have two array lists one producer array list and one consumer array list denoted by a and b
P1 P2 P3 P4 P5
5 6 7 8 9
C1 C2 C3 C4 C5
2 3 4 5 6
Now we find all those producer consumer pairs which satisfy the criteria Pi>=Ci
We have the following sets
(5,2)(6,2)(7,2),(8,2),(9,2)
(5,3)(6,3)(7,3),(8,3),(9,3)
(5,4)(6,4)(7,4),(8,4),(9,4)
(5,5)(6,5)(7,5),(8,5),(9,5)
(6,6)(7,6)(8,6),(9,6)
Let us done each of them with Si
so we have S1,S2,S3,S4,S5
we assign a third parameter called weight to each element in Si which has satisfied the condition Pi>=Ci;
so we we will have
(5,2,ai),(6,2,bi),(7,2,ci)....etc for S1
similarly for S2 and so on.
We need to find in each set Si the the pair which has the smallest weight.
if we have (5,2,3) and (6,2,4) then 5,2,3 should be chosen.We should make sure that there is only one pair in every set which is finally chosen on the basis of weight.
Suppose we get a pair (5,2,3) in S1 and (5,2,3) in S2 we should see that (5,2,3) is not used to compare to compare with any other elements in the same set S2,
Finally we should arrive at the best element pair in each set.They should be non repeating in other sets.
Given a problem
P0 P1 P2 P3 P4
9 5 2 2 8
6 5 4 5 3
C0 C1 C2 C3 C4
we have So as (P0,C0) and (P4,C0)
assuming that the one with the smaller index has lesser weight PO is selected.In the program I have used random weights.from set S1 we select the pair PO,CO
S1 =(P0,C1),(P1,C1) and (P4,C1)
since P0 and P4 are already used in previous set we dont use them for checking in S1 so we have (P1,C1) as best.
S2=(P0,C2),(P1,C2) and (P4,C2) so we dont use P0,C2 and P1 and C2 because PO and P1 are already used in S1.
So we choose P4,C2
in S3 and S4 ae have (P0,C3),(P1,C3),(P4,C3) so we dont choose anything
and same in S4 also.
So answer is
(P0,C0),(P1,C1) and (P4,C2).
I need help to write this program to do this.
Thanks.
Regards
NP
Hi Mat,
I need to do this actually.
Hello All,
This is the problem I am stuck with right now.
I have two array lists one producer array list and one consumer array list denoted by a and b
P1 P2 P3 P4 P5
5 6 7 8 9
C1 C2 C3 C4 C5
2 3 4 5 6
Now we find all those producer consumer pairs which satisfy the criteria Pi>=Ci
We have the following sets
(5,2)(6,2)(7,2),(8,2),(9,2)
(5,3)(6,3)(7,3),(8,3),(9,3)
(5,4)(6,4)(7,4),(8,4),(9,4)
(5,5)(6,5)(7,5),(8,5),(9,5)
(6,6)(7,6)(8,6),(9,6)
Let us done each of them with Si
so we have S1,S2,S3,S4,S5
we assign a third parameter called weight to each element in Si which has satisfied the condition Pi>=Ci;
so we we will have
(5,2,ai),(6,2,bi),(7,2,ci)....etc for S1
similarly for S2 and so on.
We need to find in each set Si the the pair which has the smallest weight.
if we have (5,2,3) and (6,2,4) then 5,2,3 should be chosen.We should make sure that there is only one pair in every set which is finally chosen on the basis of weight.
Suppose we get a pair (5,2,3) in S1 and (5,2,3) in S2 we should see that (5,2,3) is not used to compare to compare with any other elements in the same set S2,
Finally we should arrive at the best element pair in each set.They should be non repeating in other sets.
Given a problem
P0 P1 P2 P3 P4
9 5 2 2 8
6 5 4 5 3
C0 C1 C2 C3 C4
we have So as (P0,C0) and (P4,C0)
assuming that the one with the smaller index has lesser weight PO is selected.In the program I have used random weights.from set S1 we select the pair PO,CO
S1 =(P0,C1),(P1,C1) and (P4,C1)
since P0 and P4 are already used in previous set we dont use them for checking in S1 so we have (P1,C1) as best.
S2=(P0,C2),(P1,C2) and (P4,C2) so we dont use P0,C2 and P1 and C2 because PO and P1 are already used in S1.
So we choose P4,C2
in S3 and S4 ae have (P0,C3),(P1,C3),(P4,C3) so we dont choose anything
and same in S4 also.
So answer is
(P0,C0),(P1,C1) and (P4,C2).
My program is trying to assign weights and I am trying to print the weights along with the sets.It doesnt work fine.I need help to write this program to do this.
Thanks.
Regards.
NP
