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

Question

我有一个 ArrayList>，其中包含未定义数量的 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 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 中的每个值对 并将所有整数放入一个集合中，以确保我只得到唯一的数字。最终，我返回最短的集合（即具有最多重复整数的集合）。

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
}

PART B 工作得很好，但是我如何修改 A，以便它能够处理与 3 不同的条件大小？我现在对值 (0,1,2) 进行了硬编码，因为我不知道如何针对更大的集合修改它。

我已经花了这么多时间在这个问题上，我觉得答案并不是特别困难。

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

Answer 1

如何修改 A，以便它能够遍历条件的大小
与 3 不同？我现在对值 (0,1,2) 进行了硬编码，
因为我不知道如何修改它以适应更大的集合。

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

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

例如，对于您的数据集：

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

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

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

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]

Answer 2

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

    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 时，我指的是您当前如何使用它们。