Results 1 to 4 of 4
Thread: Discrete Mathematics Question
 12082010, 06:31 PM #1Member
 Join Date
 Dec 2010
 Posts
 2
 Rep Power
 0
Discrete Mathematics Question
i need help with complicated question.
i need to find and print all the options to create subgroups from the numbers
: 1,2,3,4,5,6,7,8,9,10
in each option i need to use with all the numbers.
for example with just the numbers 1,2,3,4
the output will be:
two groups
option 1: (1) (2,3,4)
option 2: (2) (1,3,4)
option 3: (3) (2,1,4)
option 4: (4) (2,3,1)
option 5: (1,2)(3,4)
option 6: (1,3)(2,4)
option 7: (1,4)(2,3)
three groups
option 8: (1)(2)(3,4)
option 9: (1,2)(3)(4)
option 10: (1,3)(2)(4)
.........
.......
four group
(1)(2)(3)(4)
one group
(1,2,3,4)
sorry on my english
thanks alot !!
 12082010, 08:29 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,728
 Blog Entries
 7
 Rep Power
 21
That's the set partitioning problem; for a set of one element there's only one partition { a }; for a set of two elements there are two partitions { ab, { a b } }. The general recursive rulie is: given all partitions for a set of n1 elements construct the partitions for a set of n elements as follows: add the new element to every set and create new partitions by taking the old partitions and adding a new one element partition containing the new element. The following code does just that:
Java Code:import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class SetPart { static public List makeSetPart(String set) { if (set == null  set.length() == 0) return new ArrayList(new ArrayList()); if (set.length() == 1) { List elm= new ArrayList(); elm.add(set); List sp= new ArrayList(); sp.add(elm); return sp; } List prv= makeSetPart(set.substring(1)); List sp = new ArrayList(); String first= set.substring(0, 1); for (int i= 0, n= prv.size(); i < n; i++) { List elm= new ArrayList((List)prv.get(i)); elm.add(first); sp.add(elm); } for (int i= 0, n= prv.size(); i < n; i++) { List elm= (List)prv.get(i); for (int j= 0, m= elm.size(); j < m; j++) { List old= new ArrayList(elm); old.set(j, first+(String)old.get(j)); sp.add(old); } } return sp; } public static void main(String[] args) { List l= makeSetPart("abcd"); for (Iterator i= l.iterator(); i.hasNext(); ) System.out.println(i.next()); } }
Java Code:[d, c, b, a] [cd, b, a] [bd, c, a] [d, bc, a] [bcd, a] [ad, c, b] [d, ac, b] [d, c, ab] [acd, b] [cd, ab] [abd, c] [bd, ac] [ad, bc] [d, abc] [abcd]
JosLast edited by JosAH; 12082010 at 08:50 PM.
cenosillicaphobia: the fear for an empty beer glass
 12092010, 11:19 AM #3Member
 Join Date
 Dec 2010
 Posts
 2
 Rep Power
 0
thank u great!
i just want to know how i can convert the output from " Iterator" (i.next()) to array(int[]) or string.
i mean after the function will finish i want each option in each separate array (for each option)
thank u!!!!
 12092010, 12:05 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,728
 Blog Entries
 7
 Rep Power
 21
You're welcome; my method simply returns a List containing all partitions of a set (given in String form) because that was the essential part of your question. My test program just prints the entire list. It's up to you what you want to do with the List. I'm not going to split the List for you; you have to show some effort first.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

Question concerning question marks and colons
By jim01 in forum New To JavaReplies: 17Last Post: 01142011, 01:05 AM 
Question mark colon operator question
By orchid in forum Advanced JavaReplies: 9Last Post: 12192010, 09:49 AM 
Do while question
By felito in forum New To JavaReplies: 14Last Post: 11102010, 08:46 PM 
Question about JMF
By Supamagier in forum Advanced JavaReplies: 0Last Post: 05232009, 12:04 PM 
question
By ayoood in forum Java SoftwareReplies: 6Last Post: 07072008, 02:32 PM
Bookmarks