Results 1 to 4 of 4
  1. #1
    asafavi is offline Member
    Join Date
    Dec 2010
    Posts
    2
    Rep Power
    0

    Default 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 !!

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by asafavi View Post
    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.
    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 n-1 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());
    	}
    }
    Sorry, it's old code (before generics saw the light) but don't pay any attention to the compiler warnings. The output of this little program is:

    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]
    kind regards,

    Jos
    Last edited by JosAH; 12-08-2010 at 07:50 PM.
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    asafavi is offline Member
    Join Date
    Dec 2010
    Posts
    2
    Rep Power
    0

    Default

    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!!!!

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by asafavi View Post
    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!!!!
    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,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Question concerning question marks and colons
    By jim01 in forum New To Java
    Replies: 17
    Last Post: 01-14-2011, 12:05 AM
  2. Question mark colon operator question
    By orchid in forum Advanced Java
    Replies: 9
    Last Post: 12-19-2010, 08:49 AM
  3. Do while question
    By felito in forum New To Java
    Replies: 14
    Last Post: 11-10-2010, 07:46 PM
  4. Question about JMF
    By Supamagier in forum Advanced Java
    Replies: 0
    Last Post: 05-23-2009, 11:04 AM
  5. question
    By ayoood in forum Java Software
    Replies: 6
    Last Post: 07-07-2008, 01:32 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •