Results 1 to 12 of 12
Thread: Recursion with loops
 05302011, 08:37 PM #1Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
Recursion with loops
Hi all,
im working with undirected unweighted graph, and want to get all of the combinations of two sets, where user inputs the number of verticies for each set, and each vertex of one set must not have any edge connected to any vertex of an other set. So, to get to the point, ive implemented this method for set of size 1 and of size 2, which looks like this:
Java Code:public void sets(int num) { List<String> m = new ArrayList<String>(vertEdge.keySet()); if(num== 1) { List<Set<String>> blue = new ArrayList<Set<String>>(); List<Set<String>> red = new ArrayList<Set<String>>(); int[] rec = new int[num*2]; //this could come in handy for recursive way, i think? for(rec[0] = 0; rec[0] < vertEdge.size(); rec[0]++) { for(rec[1] = 0; rec[1] < vertEdge.size() && [B]rec[1] != rec[0][/B]; rec[1]++) { if([I]!vertEdge.get(m.get(rec[0])).contains(m.get(rec[1]))[/I]) { Set<String> visited1 = new HashSet<String>(); Set<String> visited2 = new HashSet<String>(); for(int a = 0; a < num*2; a++) { if(a < num) visited1.add(m.get(rec[a])); else visited2.add(m.get(rec[a])); } if(!((blue.contains(visited1) && red.contains(visited2))  (blue.contains(visited2) && red.contains(visited1)))) { blue.add(visited1); red.add(visited2); } } } } //just for the output for(int a = 0; a < blue.size(); a++) System.out.println(blue.get(a)+ "  " + red.get(a)); } else if(num== 2) { List<Set<String>> blue = new ArrayList<Set<String>>(); List<Set<String>> red = new ArrayList<Set<String>>(); int[] rec= new int[num*2]; for(rec[0] = 0; rec[0] < vertEdge.size(); rec[0]++) { for(rec[1] = 0; rec[1] < vertEdge.size(); rec[1]++) { for(rec[2] = 0; rec[2] < vertEdge.size(); rec[2]++) { for(rec[3] = 0; rec[3] < vertEdge.size(); rec[3]++) { if([I]!vertEdge.get(m.get(rec[0])).contains(m.get(rec[2])) && !vertEdge.get(m.get(rec[1])).contains(m.get(rec[2]))&& !vertEdge.get(m.get(rec[0])).contains(m.get(rec[3])) && !vertEdge.get(m.get(rec[1])).contains(m.get(rec[3]))[/I] /*one type of conditions*/ && [B]rec[3] != rec[2] && rec[3] != rec[1] && rec[3] != rec[0] && rec[2] != rec[1] && rec[2] != rec[0] && rec[1] != rec[0][/B] /*second type of conditions*/) { Set<String> visited1 = new HashSet<String>(); Set<String> visited2 = new HashSet<String>(); for(int a = 0; a < num*2; a++) { if(a < num) visited1.add(m.get(rec[a])); else visited2.add(m.get(rec[a])); } if(!((blue.contains(visited1) && red.contains(visited2))  (blue.contains(visited2) && red.contains(visited1)))) { blue.add(visited1); red.add(visited2); } } } } } } //just for the output for(int a = 0; a < blue.size(); a++) System.out.println(blue.get(a)+ "  " + red.get(a)); } //... }
Ty for help!Last edited by Claymz; 05312011 at 12:16 PM.
 05302011, 09:20 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,365
 Blog Entries
 7
 Rep Power
 20
First construct the sets of connected vertices (see below); Name those sets S1, S2, S3 ... Sn. If is easy to construct two sets out of those sets. Constructing a set S of connecting vertices is done as follows:
1) Let S be Stemp  Sperm (two disjoint empty subsets)
2) add any vertex to Stemp
3) for any vertex v in Stemp, move it to Sperm
4) for any vertex vc with an edge connecting to v and not in S already, add it to Stemp
5) go to step 3
If step 3) fails you're ready with S1 and if there are any remaining vertices is the graph start over and construct a new set. (set S2 and again if needed for S3 etc.)
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 05302011, 10:30 PM #3Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
Im sorry, i dont completely understand your explanation, could you type it in pseudo code or something? Because im quite tired of trying different tactics and would appreciate such a favor, and am quite short on time and want to move on, if its not too much of course!
 05312011, 09:50 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,365
 Blog Entries
 7
 Rep Power
 20
 05312011, 12:07 PM #5Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
But what does the set contain? Only such a number of verticies that i need in some case (if num is 2 then 2 and so one), or all of the possible "paths" between them, and then i just need to get ones with the specified number of verticies in it?
 05312011, 12:21 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,365
 Blog Entries
 7
 Rep Power
 20
cenosillicaphobia: the fear for an empty beer glass
 05312011, 12:45 PM #7Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
Here are all the verticies and corresponding connected(neighbour) verticies for each of them. Let me remind you that the graph is conncted. I made picture to show just how it looks:
D: [B, C]
E: [F]
F: [C, A, E]
A: [B, F]
B: [A, D]
C: [D, F]
So, for this example, how would i do it?
For num = 1 i need to get the following:
[E]  [D]
[F]  [D]
[A]  [D]
[A]  [E]
[B]  [E]
[B]  [F]
[C]  [E]
[C]  [A]
[C]  [B]
and for num = 2:
[D, B]  [E, F]
[D, C]  [E, A]
[E, C]  [A, B]
I got this working with the code above, but need a recursive way, or, i need to make it like you suggested, but i dont understand your explanation, as stated before.
Ty!Last edited by Claymz; 05312011 at 12:49 PM.
 05312011, 01:27 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,365
 Blog Entries
 7
 Rep Power
 20
Hold on for a second; I think my algorithm solves an entirely different question. This was your original question:
each vertex of one set must not have any edge connected to any vertex of an other set.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 05312011, 02:07 PM #9Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
Yes. I need to get two sets out of this graph, which both contain num number of verticies, which can be any vertex on graph. the only restriction is that, verticies of one set must not have any direct edge, which would be connected to vertex of second set. Which means, i need to get two sets of verticies, which both contain num number of any verticies from the graph, but the two sets must not be connected directly (e.g. verticies of one set must not have any direct (edge) connection to verticies of the other set). However, they can be connected indirectly, which means that between each vertex of one set and each vertex of the other set, must be at least one vertex, which seperates them, or no vertex at all. And i need to get all possible combinations of such sets.
Look at the example for num = 2:
[D, B]  [E, F]
[D, C]  [E, A]
[E, C]  [A, B]
For first combination, D and B (all verticies of one set) have no direct connection with E and F (all verticies of the other set). For example, [B, D]  [C, F] would not be an option, as D and C are connected directly.Last edited by Claymz; 05312011 at 02:25 PM.
 05312011, 02:19 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,365
 Blog Entries
 7
 Rep Power
 20
If num == n need both sets contain n vertices or would the 'solution' for num == 3: {a, e, f}  {d} be ok?
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 05312011, 03:22 PM #11Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
They both need exact same number of verticies, in your case, 3.
 06012011, 08:30 PM #12Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
Similar Threads

N while loops into recursion
By Claymz in forum New To JavaReplies: 1Last Post: 04172011, 03:05 PM 
[SemiBeginner] (nested loops) What's wrong with my code? (nested loops)
By Solarsonic in forum New To JavaReplies: 20Last Post: 03222011, 04:02 AM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 06:26 PM 
Recursion
By kathyla18 in forum New To JavaReplies: 2Last Post: 04092009, 02:26 AM 
help with recursion
By Nari in forum New To JavaReplies: 15Last Post: 04242008, 09:13 AM
Bookmarks