Java 从多个数组生成所有可能的排列

Question

我有一个 ArrayList<ArrayList<int[]>>，它有一个未定义的 int[]。

示例输入（注意文本“= Condition 0/1/2”不是 ArrayList 的一部分）。

= Condition 0 
[2, 6], [3, 7]
= Condition 1
[1, 3], [2, 4], [2, 3]
= Condition 2
[1, 2]

（A 部分） 我希望创建所有 int[] 对（ArrayList<int[]> option = new ArrayList<>();，第 9 行）的所有可能排列，前提是只有一对从每个条件，例如第一个来自 C0，第二个来自

[2,6], [1,3], [1,2]
[2,6], [2,4], [1,2]
[2,6], [2,3], [1,2]
[3,7], [1,3], [1,2] 
and so on...

（B 部分） 一旦我有了所有可能的排列 (2^numOfConditions)，我将 ArrayList<int[]> pairs 中的每个值组合起来并将所有整数放入一个集合中当然我只得到唯一的数字。最终，我 return 最短的集合（即具有最多重复整数的集合）。

public static Set<Integer> findOptimalPairs(ArrayList<ArrayList<int[]>> conditions) {
// A
        ArrayList<ArrayList<int[]>> listOfConditions = new ArrayList<>();

        for (int i = 0; i < conditions.get(0).size(); i++) {
            for (int j = 0; j < conditions.get(1).size(); j++) {

                for (int k = 0; k < conditions.get(2).size(); k++) {
                    ArrayList<int[]> option = new ArrayList<>();

                    option.add(conditions.get(0).get(i));
                    option.add(conditions.get(1).get(j));
                    option.add(conditions.get(2).get(k));
                    listOfConditions.add(option);
                }
            }
        }
//A

//B
        Set<Integer> best = new HashSet<>();
        for (ArrayList<int[]> pairs : listOfConditions) {
            Set<Integer> curr = new HashSet<>();
            for (int[] pair : pairs) {
                for (int num : pair) curr.add(num);
            }
            best = (best.size() > 0 && best.size() <= curr.size()) ? best : curr;
        }

        return best;
//B
}

B 部分 工作正常，但我如何修改 A，以便它能够通过条件的大小与 3 不同？我现在硬编码了值 (0,1,2)，因为我不知道如何为更大的集合修改它。

已经花了这么多时间在这上面，我觉得答案不是特别难。

Java 11，如果这很重要的话。谢谢。

Answer 1

像这样的东西应该可以工作

    public static void setListOfConditions(ArrayList<ArrayList<int[]>> conditions, ArrayList<ArrayList<int[]>> listOfConditions, int depth, ArrayList<Integer> indices){
    // when we get to the end then this code creates and adds the option to listOfCondition. This would be equivalent to the code you have inside all the for-loops.
    if (conditions.size() == depth){
        ArrayList<int[]> option = new ArrayList<>();
        // this loop does what the lines
        // option.add(conditions.get(0).get(i)); etc
        // did in your code.
        for (int l = 0; l < indices.size(); l++) {
            option.add(conditions.get(l).get(indices.get(l)));
        }
        // add to listOfConditions
        listOfConditions.add(option);
        
        // remove the last index such that it can be changed.
        indices.remove(indices.size()-1);
        return;
    }
    // recursive call to the function in a for-loop.
    for (int k = 0; k < conditions.get(depth).size(); k++) {

        // the variable indices contains for example i,j,k values. Here we make sure that i,j and k have the correct values.
        // In the first iteration we get a list of the number 0. (You can think of this as the start of your first loop when i = 0.)
        // In every iteration after that we keep adding indices.
        // Example iteration1: i = 0
        // Example iteration2: i = 0, j = 0
        // Example iteration3: i = 0, j = 0, k = 0
        // In this example we have reached the end so the code inside the if-statement will be run.
        try {
            indices.set(depth, k);
        } catch (IndexOutOfBoundsException e) {
            indices.add(depth, k);
        }

        // recursive call to the function where depth is increased everytime.
        setListOfConditions(conditions, listOfConditions, depth + 1, indices);
    }
}

public static Set<Integer> findOptimalPairs(ArrayList<ArrayList<int[]>> conditions) {
    // A
    ArrayList<ArrayList<int[]>> listOfConditions = new ArrayList<>();

    // this function gives all the conditions by adding them to listOfConditions.
    setListOfConditions(conditions,listOfConditions,0,new ArrayList<>());
    // A

    // B
    Set<Integer> best = new HashSet<>();
    for (ArrayList<int[]> pairs : listOfConditions) {
        Set<Integer> curr = new HashSet<>();
        for (int[] pair : pairs) {
            for (int num : pair) curr.add(num);
        }
        best = (best.size() > 0 && best.size() <= curr.size()) ? best : curr;
    }

    return best;
    // B
}

在您的代码中，您有循环内循环。在这里，我们使用递归调用来执行 for 循环。我试图与您当前拥有的代码进行比较。因此，当我在评论中提到 i、j、k 时，我指的是您当前如何使用它们。

Answer 2

how can I modify A, so it will be able to go through conditions' sizes that are different from 3? I hardcoded the values (0,1,2) for now, because I have no idea how to modify it for larger collections.

基本上，您创建一个一维数组，该数组将在每个索引处保存该集合的 int[] 数组的数量。

然后您创建一个额外的相同大小的一维数组，并使用存储的大小“计数”以了解何时重置每个计数器。如果你曾经在其他基础上计算过，你应该确切地知道我的意思，除了我们将左侧视为最低有效数字。

例如，您的数据集：

[2, 6], [3, 7]
[1, 3], [2, 4], [2, 3]
[1, 2]

共有三行，因此您需要创建一个大小为 3 的数组，并存储每组中的项数。

我在这里hard-coding只是为了展示这个过程。在实际代码中，它将根据传入的数据动态变化：

int[] setSize = {2, 3, 1};

现在我们开始一个相同大小的新数组，所有值都为零（无论如何这是默认值）：

int[] counters= {0, 0, 0}

从左边开始，我们递增该索引中的值，直到达到“设置大小”。每当我们点击“设置大小”时，我们都会将该索引重置为零并将该列递增到右侧（对每一列的重置和递增都遵循相同的规则）。

这些将是生成的序列：

[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 2, 0]
[1, 2, 0]

这些数字表示您应该从该组合中的每个集合中选择 int[] 数组中的哪个索引。那么我们只需将这些索引转换为输入数据集中相应的 int[] 数组。

这种方法是迭代的，不需要递归。

代码可能如下所示：

import java.util.*;
import java.util.ArrayList;

class Main {
 
  public static void main(String[] args) {   
    ArrayList<ArrayList<int[]>> conditions = new ArrayList<ArrayList<int[]>>();
    ArrayList<int[]> condition1 = new ArrayList<int[]>();
    condition1.add(new int[] {2,6});
    condition1.add(new int[] {3,7});
    conditions.add(condition1);
    ArrayList<int[]> condition2 = new ArrayList<int[]>();
    condition2.add(new int[] {1,3});
    condition2.add(new int[] {2,4});
    condition2.add(new int[] {2,3});
    conditions.add(condition2);
    ArrayList<int[]> condition3 = new ArrayList<int[]>();
    condition3.add(new int[] {1,2});
    conditions.add(condition3);

    System.out.println("Input Data:");
    display(conditions);
    
    System.out.println();    
    ArrayList<ArrayList<int[]>> combos = findOptimalPairs(conditions);
    
    System.out.println("Output Data:");
    display(combos);
  }

  public static void display(ArrayList<ArrayList<int[]>> data) {
    for(ArrayList<int[]> set : data) {
      for(int i=0; i<set.size(); i++) {
        System.out.print(Arrays.toString(set.get(i)));
        if (i<(set.size()-1)) {
          System.out.print(", ");
        }        
      }
      System.out.println();
    }
  }
  
  public static ArrayList<ArrayList<int[]>> findOptimalPairs(ArrayList<ArrayList<int[]>> conditions) {
    ArrayList<ArrayList<int[]>> combos = new ArrayList<ArrayList<int[]>>();
    
    int combinations = 1;
    int[] setSize = new int[conditions.size()];
    for(int i=0; i<conditions.size(); i++) {
      ArrayList<int[]> set = conditions.get(i);
      int size = set.size();
      setSize[i] = size;
      combinations = combinations * size;
    }

    int[] counters = new int[setSize.length];
    for(int i=0; i<combinations; i++) {
      ArrayList<int[]> combo = new ArrayList<int[]>();      
      for(int j=0; j<counters.length; j++) {
        combo.add(conditions.get(j).get(counters[j]));
      }
      combos.add(combo);
      
      for(int j=0; j<counters.length; j++) {
        if (counters[j]<(setSize[j]-1)) {
          counters[j]++;
          break;
        }
        else {
          counters[j] = 0;
        }
      }
    }
    
    return combos;
  }
  
}

生成的输出：

Input Data:
[2, 6], [3, 7]
[1, 3], [2, 4], [2, 3]
[1, 2]

Output Data:
[2, 6], [1, 3], [1, 2]
[3, 7], [1, 3], [1, 2]
[2, 6], [2, 4], [1, 2]
[3, 7], [2, 4], [1, 2]
[2, 6], [2, 3], [1, 2]
[3, 7], [2, 3], [1, 2]

Java 从多个数组生成所有可能的排列

Java Generate all possible permutations from multiple arrays

java

arraylist

permutation

set