基于广度级别的整数数组分区方法

Question

我想对初始数组 (dF) 进行分区，并根据广度级别方法对获得的分区迭代执行相同操作。从初始数组 (dF) 开始，如果在两个数组上满足特定条件（请参阅下面的 partition_array_(dF, intIter, listMed)；生成 2 个整数数组），则获得两个数组，并且对每个获得的数组重复该过程分区（广度级别明智）直到不再满足内部条件然后我想return获得分区的最后一级。

根据从另一个整数数组 intIter 中迭代选择的值 int 进行分区。我的迭代方法如下：

 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.我希望这个算法return只最后一层children分区（最后一个for循环得到的最小数组）[= =17=]

2. 确保算法在没有新分区时停止获得。

我想确定它的逻辑是否正确。

其他问题：是否有任何算法优化可以使代码更紧凑？

输入：列表：[1,2,4,5,7,8,10,11]； ListMed 数组列表：[6,3,9] intIter 是 listMed 迭代值之一。

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

driver代码：

          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);

Answer 1

我相信此代码与递归广度优先算法等效且更紧凑。当没有更多的分区可以完成时它停止：

    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();
    }

要分区的列表存储在toPartition中。当它们不再可分区时，它们将累积在 noMorePartitionable 中。一旦 toPartition 为空，返回 noMorePartitionable。

基于广度级别的整数数组分区方法

Breadth level based partitioning approach for arrays of integers

java

algorithm

partitioning

java-8

partition