Algorithm for finding all possible list splits

Question

I am working with a linked list that I created that contains a set of numbers as data. I need to find a way to check all possible two sets of sections of this list for something, and for this I need to break the list into all kinds of combinations with two sets. The 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 4-digit list is not complicated, but things get complicated as the list grows larger and I can’t see the template. Can someone help me find an algorithm for this?

Edit:

Sorry, I did not see the question. This is what I have tried so far. My loop structure is incorrect. When I find out what I'm doing after checking for a regular array, I will expand 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 (correct) subsets of a given set, except for additional ones. If your list has n items, you will have 2 ^ n subsets. But since you do not need an empty subset, and you want to identify the (A, B) section with (B, A), you get 2 ^ (n-1) -1 partitions.

To list them, you can define a section with a binary number with n digits, where the number 0 at position k means that the k-th element of the list is in the first set of your section, 1 means that it is in the second. You want to identify a number with its extra (exchanging the set with another), and you want to exclude 0 (an empty subset).

This way you can use bitwise operations. The XOR operator gives you an extra unit. So 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 what you were looking for? If not, let me know and I will make adjustments or add comments as necessary.

Answer 3

Using linked lists to store subsets is actually quite perfect - the code will be easier to combine than using arrays.

Write a recursive function that builds subsets. He will accept the following arguments:

• Entry List
• List "output"
• vector of results (it will be a “collection parameter” if it means something to you)

Here is an example code sketch in Ruby:

  # 'input', and 'output' are linked-list nodes # we'll assume they have 'value' and 'next' attributes # we'll further assume that a new node can be allocated with Node.new(value,next) # the lists are null-terminated def build_subsets(input, output, results) if input.nil? results << output else item = input.value input = input.next build_subsets(input, Node.new(item, output), results) build_subsets(input, output, results) end end 

Call it something like this:

  results = [] build_subsets(list, nil, results) 

After tha, all subsets will be in results . I know you need a Java translation, but it should be easy to translate to Java. I am just giving you an idea of ​​how code can work.