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<>();
        Integer currentInt  = new Integer();
        boolean first = true;
        partitions_.add(dF);
        while ( partitions_.size()!=0 || first == true) {
            first = false;
            currentInt  = intIter.next();
            else intIter = listMed.iterator();
            List<Integer> poppedTop = partitions_.get(partitions_.size()-1);
            int numberPartsBf = partitions_.size();
            partitions_.addAll(partition_array_(poppedTop, currentInt , listMed));
            int numberPartsAf = partitions_.size();
            if (numberPartsAf > numberPartsBf && partitions_.contains(poppedTop)) partitions_.remove(poppedTop);
            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);

CodePudding user response：

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.