Discrete Mathematics Question

[asafavi]

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

[JosAH]

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:

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:

[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

[asafavi]

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

[JosAH]

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