How to find all possible splits of a set?

Question

I need to split a set A into two sets B and C, and find all possible splits of A' elements in B and C.

So when first split size is 2 then

[abcd] ->[ab] [cd], [ac] [bd], [cd] [ab]..

And when first split size is 1 then

[abcd] -> [b] [acd], [a] [bdc], [d] [abc]..

Any idea how this can be done?

You are trying to create all permutations for a given length. This one is for strings, but the technique is the same: http://www.geeksforgeeks.org/print-all-combinations-of-given-length/ — Flocke, Jan 09 '16 at 13:21
it is not permutation. abcd and bacd are different permutations but if you split in middle. Both splits are same. This is a combination problem. — prem kumar, Jan 09 '16 at 13:28

score 1 · Accepted Answer · answered Jan 09 '16 at 14:08

1

you can use apache commons math util for java. If your are using maven add its dependency in pom otherwise manually download and add the jar.

https://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/Combinations.html

//n is no of elements. k is k-combinations
public Combinations(int n, int k)

//you can use this method to get every combination    
public Iterator<int[]> iterator()

This will give you all k-combinations and values will be in terms of indexes. you need to convert index to element.

if array arr, you can do arr[i]. if list, list.get(i)

answered Jan 09 '16 at 14:08

prem kumar

5,641
3
24
36

That worked like a charm! For my example above I set N=4 and k=2, iterate over all k-combinations, use them as indexes for A (so I got the first split) and then remove those from a copy of A (which is the second split). – Sylar Jan 10 '16 at 02:51
1

cool. instead of creating another copy of A, you can have a set(or list) which contains integers. Initialize with all indexes and then you can use set.removeAll(Arrays.asList(first split int[])) to get second split indexes. may reduce the no of lines. if you do it this way, you will always have one copy of A and splits are identified by the indexes. If you want it resolved, you can use A[i] anytime. Point is try to avoid duplicating the Original array so your code will be neat and easy to understand. – prem kumar Jan 10 '16 at 07:31

score 1 · Answer 2 · edited Jan 10 '16 at 09:31

Do you mean an algorithmn like this? I wrote it quickly an hopefully it helps:

public void split(int s, String list1, String list2){
    if(s > list1.length()){
        System.err.println("To big s");
        return;
    }
    if(s == 0){
        System.out.println(list2 + " "+ list1);
        return;
    }
    for(int i = 0; i < list1.length(); i++){
            String temp = list1.substring(0, i) + list1.substring(i+1, list1.length());
            String temp2 = list2 + list1.charAt(i);
            split(s-1, temp, temp2);
    }       
}

How to find all possible splits of a set?

2 Answers2

Linked