Algorithm to find all possible splits of a list

Question

I am working with a linked list that I created which contains a set of numbers as data. I need to find a way to test every possible two-set partition of this list for something, and to do that, I need to break the list into every possible two-set combination. Order is not important and there will be duplicates.

For instance, for a list of numbers {1 4 3 1}, the possible splits are 

{1} and {4, 3, 1}
{4} and {1, 3, 1}
{3} and {1, 4, 1}
{1} and {1, 4, 3}
{1, 4} and {3, 1}
{1, 3} and {4, 1}
{1, 1} and {4, 3}

A list of 4 numbers is not difficult, but things become more complicated as the list grows larger, and I am having trouble seeing a pattern. Can anyone help me find an algorithm for this?

Edit:

Sorry, I didn't see the question. This is what I have tried so far. My loop structure is wrong. When I figure out what I am doing after trying on a regular array, I will extend the algorithm to fit my linked list.

public class TwoSubsets
{
    public static void main(String[] args)
    {
        int[] list = {1, 3, 5, 7, 8};
        int places = 1;

        int[] subsetA = new int[10];
        int[] subsetB = new int[10];


        for (int i = 0; i < list.length; i++)
        {
            subsetA[i] = list[i];       
            for (int current = 0; current < (5 - i ); current++)
            {
                subsetB[current] = list[places];        
                places++;

            }

            System.out.print("subsetA = ");
            for (int j = 0; j < subsetA.length; j++)
            {
                System.out.print(subsetA[j] + " ");
            }

            System.out.println();
            System.out.print("subsetB = ");
            for (int k = 0; k < subsetB.length; k++)
            {
                System.out.print(subsetB[k] + " ");
            }



        }
    }

}

Answer 1

So you are looking for all (proper) subsets of a given set, apart from complementary ones. If your list has n elements, you would have 2^n subsets. But since you don't want the empty subset and you want to identify the partition (A,B) with (B,A) you get 2^(n-1)-1 partitions.

To enumerate them you could identify a partition with a binary number with n digits where a digit 0 in position k means that the k-th element of the list is in the first set of your partition, 1 means that it is in the second one. You want to identify a number with its complementary (exchanging a set with the other) and you want to exclude 0 (empty subset).

So you can use bitwise operations. The XOR operator gives you the complementary subdivision. So something like the following should work:

int m = (1<<n)-1; // where n is the number of elements, m=111111...11 in binary
for (int i=0;i<m-1;++i) {
    if (i>(m^i)) continue; // this was already considered with 0 and 1 exchanged
    // here the binary digits of i represent the partition
    for (int j=0;j<n;++j) {
       if ((1<<j) & i) {
          // the j-th element of the list goes into the second set of the partition
       } else {
          // the j-th element of the list goes into the first set of the partition
       }
    }
}

Answer 2

Code:

public static void main(String[] args) {
    for(String element : findSplits(list)) {
        System.out.println(element);
    }        
}

static ArrayList<String> findSplits(ArrayList<Integer> set) {
    ArrayList<String> output = new ArrayList();
    ArrayList<Integer> first = new ArrayList(), second = new ArrayList();
    String bitString;
    int bits = (int) Math.pow(2, set.size());
    while (bits-- > 0) {
        bitString = String.format("%" + set.size() + "s", Integer.toBinaryString(bits)).replace(' ', '0');
        for (int i = 0; i < set.size(); i++) {
            if (bitString.substring(i, i+1).equals("0")) {
                first.add(set.get(i));
            } else {
                second.add(set.get(i));
            }
        }
        if (first.size() < set.size() && second.size() < set.size()) {
            if (!output.contains(first + " " + second) && !output.contains(second + " " + first)) {
                output.add(first + " " + second);
            }
        }
        first.clear();
        second.clear();
    }
    return output;
}

Output:

[1] [1, 4, 3]
[3] [1, 4, 1]
[3, 1] [1, 4]
[4] [1, 3, 1]
[4, 1] [1, 3]
[4, 3] [1, 1]
[4, 3, 1] [1]

Is this along the lines of what you were looking for? If not, let me know and I will make adjustments or add comments as necessary.