Split n-size array into k-boxes

Question

I am trying to write a program that given an n-array of integers in increasing order and k-boxes, it splits the original array into the boxes of consecutive numbers, that is, as they appear in the input order

So far I have written the following code

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

However, the problem with my code is that I have hardcoded the loops and the k-boxes and I am not sure how to resolve my problem.

The goal of the function is to generate all possibilities of element placement in each box.

Any help or ideas for the algorithm are appreciated!

Answer 1

When searching a bit I came across this answer. You can use this to get all possible partitions of your input-list. You'll have to make one small modification to that code: holder.addAll(b); becomes holder.addAll(0,b);, so the values of b are added at the front instead of end, which means the original order is mostly retained instead of reversed.

After that you can use two filters:

• One to check that all values in a (flattened) partition are still in the original order, removing any that are not.
• And one to filter it based on the amount of chunks k (for which I've used a Java 8+ stream-filter).

Here a possible solution:

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

Which outputs:

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.

Answer 2

Depending on this wekipedia post stars and bars and a similar answer of mine for somehow related question here on SO, here is another way without streams:

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7};
    int k = 3;
    permute(arr,k);
}

public static void permute(int [] arr, int k ) {
    int combinations = (int) Math.pow(2, arr.length - 1);
    List<List<List<Integer>>> result = new ArrayList<>();
    for (int i = 0; i < combinations; i++) {
        String operators = String.format("%" + (arr.length - 1) + "s", Integer.toBinaryString(i)).replace(' ', '0');

        int count = 0;
        List<List<Integer>> tempListOfList = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        for (int x = 0; x < operators.length(); x++) {                
            tempList.add(arr[x]);
            if (operators.charAt(x) == '0') {
                if(count < k-1){
                    tempListOfList.add(tempList);
                    tempList = new ArrayList<>();                    
                }
                count++;
            }                
        }            
        tempList.add(arr[arr.length-1]);
        tempListOfList.add(tempList);
        if(count == k-1){
            result.add(tempListOfList);                
        }            
    }
    for(List<List<Integer>> parts: result){
        System.out.println(parts);
    }
}