java - 将 n 大小的数组拆分为 k 盒

Question

我正在尝试编写一个程序，给定一个递增顺序的 n 整数数组和 k 盒，它将原始数组拆分为连续数字的框，即它们按输入顺序出现

到目前为止我已经写了下面的代码

int[] A = {1,2,3,4,5};
int k = 3;
int n = 5; 
for(int i = 0; i <= n - k; i++){
   for(int j = i+1; j < n-1; j++){
      int[] k1 = Arrays.copyOfRange(A, 0, i+1);
      int[] k2 = Arrays.copyOfRange(A, i+1, j+1);
      int[] k3 = Arrays.copyOfRange(A, j+1, n);
      System.out.println(Arrays.toString(k1) + "|" + Arrays.toString(k2) + "|" + Arrays.toString(k3));
   }
}

但是，我的代码存在的问题是我对循环和 k-boxes 进行了硬编码，我不确定如何解决我的问题。

该函数的目标是生成每个框中元素放置的所有可能性。

感谢您对算法的任何帮助或想法!

Answer 1

在搜索时我遇到了 this answer .您可以使用它来获取输入列表的所有可能分区。您必须对该代码进行一点小修改:holder.addAll(b);变成 holder.addAll(0,b); , 所以 b 的值添加在前面而不是末尾，这意味着原始顺序大部分保留而不是颠倒。

之后你可以使用两个过滤器:

• 用于检查(展平的)分区中的所有值是否仍按原始顺序排列，并删除任何不是原始顺序的。
• 还有一个是根据 block 的数量过滤它 k (为此我使用了 Java 8+ 流过滤器)。

这里有一个可能的解决方案:

import java.util.*;
import java.util.stream.Collectors;
class Main{
  public static void main(String[] args) {
    int[] A = {1,2,3,4,5};

    // Convert your int-array to an Integer-ArrayList:
    List<Integer> inputList = Arrays.stream(A).boxed().collect(Collectors.toList());

    // Get all possible partitions of this List:
    List<List<List<Integer>>> partitions = partition(inputList);
    System.out.println("All partitions: ");
    prettyPrintPartitions(partitions);

    // Remove all items which aren't in the original order:
    filterPartitionsByOriginalOrder(partitions, A);
    System.out.println("\nPartitions that are in the original order: ");
    prettyPrintPartitions(partitions);

    // Filter them based on amount of chunks `k`:
    for(int k=2; k<A.length; k++){
      System.out.println("\nPartitions of size "+k+" (and also in the original order): ");
      List<List<List<Integer>>> filteredPartitions = filterPartitionsByAmountOfChunks(partitions, k);
      prettyPrintPartitions(filteredPartitions);
    }
  }

  private static void prettyPrintPartitions(List<List<List<Integer>>> partitions){
    for(List<List<Integer>> partition : partitions){
      System.out.println(partition);
    }
  }

  /* Method to get all partitions (all possible ways to divide the list in a variable amount of chunks) of a List of Integers */
  private static List<List<List<Integer>>> partition(List<Integer> inputList) {
    List<List<List<Integer>>> result = new ArrayList<>();
    if(inputList.isEmpty()){
      List<List<Integer>> empty = new ArrayList<>();
      result.add(empty);
      return result;
    }
    // Note that this algorithm only works if inputList.size() < 31
    // since you overflow int space beyond that. This is true even
    // if you use Math.pow and cast back to int.
    int limit = 1 << (inputList.size() - 1);
    // Note the separate variable to avoid resetting
    // the loop variable on each iteration.
    for(int j=0; j<limit; j++){
      List<List<Integer>> parts = new ArrayList<>();
      List<Integer> part1 = new ArrayList<>();
      List<Integer> part2 = new ArrayList<>();
      parts.add(part1);
      parts.add(part2);
      int i = j;
      for(Integer item : inputList){
        parts.get(i%2).add(item);
        i >>= 1;
      }
      for(List<List<Integer>> b : partition(part2)){
        List<List<Integer>> holder = new ArrayList<>();
        holder.add(part1);
        // Add them at the start instead of end so the items hold the original order
        holder.addAll(0, b);
        result.add(holder);
      }
    }
    return result;
  }

  /* Method to filter a List of List of List of Integers (partitions) based on a given amount of chunks `k` */
  private static List<List<List<Integer>>> filterPartitionsByAmountOfChunks(List<List<List<Integer>>> partitions, int k){
    List<List<List<Integer>>> filteredPartitions = partitions.stream()
                                                             .filter(partition -> partition.size() == k)
                                                             .collect(Collectors.toList());
    return filteredPartitions;
  }


  /* Method to remove any partition that (flattened) isn't in the same order as the original given int-array */
  private static void filterPartitionsByOriginalOrder(List<List<List<Integer>>> partitions, int[] A){
    partitions.removeIf(partition -> {
      int index = 0;
      for(List<Integer> part : partition){
        for(int value : part){
          // The value is not at the same index in the original array,
          // so remove the partition
          if(value != A[index]){
            return true;
          }
          index++;
        }
      }
      return false;
    });
  }
}

哪些输出:

All partitions: 
[[1, 2, 3, 4, 5]]
[[1], [2, 3, 4, 5]]
[[2], [1, 3, 4, 5]]
[[1, 2], [3, 4, 5]]
[[1], [2], [3, 4, 5]]
[[3], [1, 2, 4, 5]]
[[1, 3], [2, 4, 5]]
[[1], [3], [2, 4, 5]]
[[2, 3], [1, 4, 5]]
[[2], [3], [1, 4, 5]]
[[1, 2, 3], [4, 5]]
[[1], [2, 3], [4, 5]]
[[2], [1, 3], [4, 5]]
[[1, 2], [3], [4, 5]]
[[1], [2], [3], [4, 5]]
[[4], [1, 2, 3, 5]]
[[1, 4], [2, 3, 5]]
[[1], [4], [2, 3, 5]]
[[2, 4], [1, 3, 5]]
[[2], [4], [1, 3, 5]]
[[1, 2, 4], [3, 5]]
[[1], [2, 4], [3, 5]]
[[2], [1, 4], [3, 5]]
[[1, 2], [4], [3, 5]]
[[1], [2], [4], [3, 5]]
[[3, 4], [1, 2, 5]]
[[3], [4], [1, 2, 5]]
[[1, 3, 4], [2, 5]]
[[1], [3, 4], [2, 5]]
[[3], [1, 4], [2, 5]]
[[1, 3], [4], [2, 5]]
[[1], [3], [4], [2, 5]]
[[2, 3, 4], [1, 5]]
[[2], [3, 4], [1, 5]]
[[3], [2, 4], [1, 5]]
[[2, 3], [4], [1, 5]]
[[2], [3], [4], [1, 5]]
[[1, 2, 3, 4], [5]]
[[1], [2, 3, 4], [5]]
[[2], [1, 3, 4], [5]]
[[1, 2], [3, 4], [5]]
[[1], [2], [3, 4], [5]]
[[3], [1, 2, 4], [5]]
[[1, 3], [2, 4], [5]]
[[1], [3], [2, 4], [5]]
[[2, 3], [1, 4], [5]]
[[2], [3], [1, 4], [5]]
[[1, 2, 3], [4], [5]]
[[1], [2, 3], [4], [5]]
[[2], [1, 3], [4], [5]]
[[1, 2], [3], [4], [5]]
[[1], [2], [3], [4], [5]]

Partitions that are in the original order: 
[[1, 2, 3, 4, 5]]
[[1], [2, 3, 4, 5]]
[[1, 2], [3, 4, 5]]
[[1], [2], [3, 4, 5]]
[[1, 2, 3], [4, 5]]
[[1], [2, 3], [4, 5]]
[[1, 2], [3], [4, 5]]
[[1], [2], [3], [4, 5]]
[[1, 2, 3, 4], [5]]
[[1], [2, 3, 4], [5]]
[[1, 2], [3, 4], [5]]
[[1], [2], [3, 4], [5]]
[[1, 2, 3], [4], [5]]
[[1], [2, 3], [4], [5]]
[[1, 2], [3], [4], [5]]
[[1], [2], [3], [4], [5]]

Partitions of size 2 (and also in the original order): 
[[1], [2, 3, 4, 5]]
[[1, 2], [3, 4, 5]]
[[1, 2, 3], [4, 5]]
[[1, 2, 3, 4], [5]]

Partitions of size 3 (and also in the original order): 
[[1], [2], [3, 4, 5]]
[[1], [2, 3], [4, 5]]
[[1, 2], [3], [4, 5]]
[[1], [2, 3, 4], [5]]
[[1, 2], [3, 4], [5]]
[[1, 2, 3], [4], [5]]

Partitions of size 4 (and also in the original order): 
[[1], [2], [3], [4, 5]]
[[1], [2], [3, 4], [5]]
[[1], [2, 3], [4], [5]]
[[1, 2], [3], [4], [5]]

Try it online.