Breadth level based partitioning approach for arrays of integers

Question

I want to partition an initial array (dF) and iteratively do the same for the obtained partitions based on a Breadth level approach. Starting from an initial array (dF) two arrays are obtained if a certain condition is met on the two arrays (see partition_array_(dF, intIter, listMed) below; that generates 2 arrays of ints) and the process is repeated for each obtained partition (Breadth level wise) up until that inner condition is no longer met then i want to return the last level of obtained partitions.

The partitioning is done according to a value int that is iteratively chosen from another array of ints intIter. My iterative method goes like the following:

 public ArrayList<List<Integer>> partition_rec(List<Integer> dF, Iterator<Integer> intIter, List<Integer> listMed) {
 ArrayList<List<Integer>> partitions_ = new ArrayList<List<Integer>>();
 ArrayList<List<Integer>> partitions_bf = new ArrayList<>();
 
 
 partitions_.add(dF);
 while ( partitions_.size()!=0) {
 
 partitions_bf = new ArrayList<>(partitions_);
 for (int j=0;j< partitions_.size();j++) {
 List<Integer> dss = partitions_bf .get(j);
 numberPartsBf = partitions_bf .size();
 if (intIter.hasNext())
 currentInt = intIter.next();
 else intIter = listMed.iterator();
 partitions_bf .addAll(partition_array_(dss, currentInt , listMed));
 numberPartsAf = partitions_bf .size();
 if (numberPartsAf > numberPartsBf && partitions_bf .contains(dss)) partitions_bf .remove(dss);
 if (j == partitions_.size()-1){
 if (partitions_.size() == partitions_bf.size()) return partitions_bf;
 partitions_ = new ArrayList<>(partitions_bf );
 break;
 
 }
 
 else if (!intIter.hasNext()) intIter = listMed.iterator();
 }
 }
 return partitions_bf ;
 }

1. I want this algorithm to return only the last level children partitions (the smallest arrays obtained by the last for loop).

2. make sure this algorithm stops when no new partitions could be obtained.

I want to make sure its logic is correct.

Other question: Is there any algorithmic optimization to do here for a more compact code ?

Input: List : [1,2,4,5,7,8,10,11]; ListMed ArrayList: [6,3,9] intIter being one of the listMed iterated values.

Output ArrayLists: [1,2], [4,5], [7,8], [10,11]

driver code :

 List<Integer> dF = {1,2,4,5,7,8,10,11};
 List<Integer> listMed = {6,3,9};
 Iterator<Integer> its = listMed.iterator();
 ArrayList<List<Integer>> res = partition_rec( dF, intIter, listMed);

• lolo101: When partition_array_(dss, currentInt, listMed) cannot partition dss it returns an empty list?
• singh raj: Yes, exactly. (i am controlling the size of partitions_ and if dss cannot be partitioned the list partitions_ will remain the same)
• lolo101: When I run the algorithm with the driver code it crashes because in the first line of the for loop you want to take the first element (get(0)) because the last element that has been partitioned is removed. So it's always the first element that is the next to partition. Did I get it right?
• lolo101: When I fixed the issue with List<Integer> dss = partitions_bf .get(j); the algorithm still crashes because when it exits the for loop, partitions_ is not empty but intIter has been consumed and then currentInt = intIter.next(); throws. If I replace the while condition with while (partitions_.size() != 0 && intIter.hasNext()) then the code yields the expected result
• singh raj: yes i check intIter.hasNext() as in the second loop OK. for your first comment: yes i remove the element that has been partitioned because at the end i want the smallest partitioned parts only. Is there still other problems ?

Answer 1

I believe this code is equivalent and more compact with a recursive breadth-first algorithm. It stops when no more partition can be done:

 public static List<List<Integer>> partition_rec(List<Integer> dF, Iterator<Integer> medIter, List<Integer> listMed) {
 List<List<Integer>> toPartition = new LinkedList<>();
 toPartition.add(dF);
 return recursion(toPartition, medIter, listMed, new ArrayList<>());
 }
 private static List<List<Integer>> recursion(List<List<Integer>> toPartition, Iterator<Integer> medIter, List<Integer> listMed, List<List<Integer>> noMorePartitionable) {
 if (toPartition.isEmpty()) return noMorePartitionable;
 medIter = reiterateIfNeeded(medIter, listMed);
 List<Integer> toPartitionHead = toPartition.remove(0);
 List<List<Integer>> partitions = partition_array_(toPartitionHead, medIter.next(), listMed);
 if(partitions.isEmpty()) noMorePartitionable.add(toPartitionHead);
 toPartition.addAll(partitions);
 return recursion(toPartition, medIter, listMed, noMorePartitionable);
 }
 private static Iterator<Integer> reiterateIfNeeded(Iterator<Integer> medIter, List<Integer> listMed) {
 return medIter.hasNext() ? medIter : listMed.iterator();
 }

The lists to partition are stored into toPartition. When they are no more partitionable they are accumulated in noMorePartitionable. Once toPartition is empty, noMorePartitionable is returned.

• singh raj: i want to return all last level obtained partitions (that's when the algo stops: when no other partitioning could be done: not when all meds have been consumed)
• lolo101: @singhraj what is the expected behavior when all meds are consumed? For instance, if meds={6,3,9} the algorithm should use 6,3,9,6,...?
• singh raj: yes it should return to the initial value (6 in the example). THe algo stops when partition_array_ couldn't yield other children for the current parent arrays
• singh raj: i can't see the stopping condition in your code mine it was at : if (j == partitions_.size()-1){ if (partitions_.size() == partitions_bf.size()) return partitions_bf; partitions_ = new ArrayList<>(partitions_bf ); break; }
• lolo101: The exit condition was if (!medIter.hasNext()) return queue; But let me edit the code to reiterate over listMed. The exit condition is now if(partitions.isEmpty()) return queue;