Java：数组的组合，每个数组 x

Question

我有一组选项池，我正在尝试动态生成组合以进行测试。我想定义存储桶并让代码生成所有组合以通过@DataProvider 提供给我的 TestNG 测试。现在我有一些硬编码的案例，但很明显这不是维护代码的最佳方式。我正在努力处理当 y > 2 时您在 y 个“桶”中有 x 个“球”的情况。在微不足道的情况下，假设您有以下示例：public static void main(String [] args){   Object[][] combinations = getCombinations(        new String[]        {          "1", "2"        },        new String[]        {          "3", "4"        }/*,        new String[]        {          "5", "6"        }*/);   for (Object[] combination : combinations)   {     System.out.println(Arrays.toString(combination));   }}private Object[][] getCombinations(Object[]... arrays){   if (arrays.length == 0)   {     return new Object[0][0];   }   List<Object[]> solutions = new ArrayList<>();   Object[] array1 = arrays[0];   for (Object o : array1)   {     for (int i = 1; i < arrays.length; i++)     {       for (Object o2 : arrays[i])       {         int count = 0;         Object[] path = new Object[arrays.length];         path[count++] = o;         path[count++] = o2;         solutions.add(path);       }     }   }return solutions.toArray(new Object[0][0]);}输出：[1, 3][1, 4][2, 3][2, 4]添加第三个“桶”会将所有东西都扔出窗外。解决方法如下：[1,3,5][1,3,6][1,4,5][1,4,6][2,3,5][2,3,6][2,4,5][2,4,6]任何想法如何解决这个问题？理想情况下，您会通过 getCombinations 每个桶的选择数量。虽然欢迎提供解决方案代码，但我对它背后的推理更感兴趣。

Answer 1

您遇到了一个过于复杂的解决方案，尽管如此，它恰好适用于两个存储桶的情况。但是，正如您所发现的，它不会自然地扩展到三个或更多存储桶。

这是一个更简单的解决方案，适用于两个桶的情况，泛型并使用Lists 代替数组：

// Find all 2-item combinations consisting of 1 item picked from 

// each of 2 buckets

static <T> List<List<T>> pick1From2(List<List<T>> in)

{

    List<List<T>> result = new ArrayList<>();

    for (int i = 0; i < in.get(0).size(); ++i) {

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

            result.add(Arrays.asList(in.get(0).get(i), in.get(1).get(j)));

        }

    }

    return result;

}

外循环遍历第一个桶的所有元素，对于第一个桶的每个元素，内循环遍历第二个桶的元素。

对于三个存储桶，您可以添加第三级循环嵌套：

// Find all 3-item combinations consisting of 1 item picked from

// each of 3 buckets 

static <T> List<List<T>> pick1From3(List<List<T>> in)

{

    List<List<T>> result = new ArrayList<>();

    for (int i = 0; i < in.get(0).size(); ++i) {

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

            for (int k = 0; k < in.get(2).size(); ++k)

                result.add(Arrays.asList(in.get(0).get(i), in.get(1).get(j), in.get(2).get(k)));

        }

    }

    return result;

}

现在您有一个外循环单步执行第一个存储桶的项目，一个中间循环单步执行第二个存储桶的项目，以及一个最内循环单步执行第三个存储桶的元素。

但是这种方法受到以下事实的限制：所需的循环嵌套深度与要处理的桶的数量直接相关：当然，您可以添加第四个、第五个等循环嵌套级别来处理四个、五个，或更多桶。但是，基本问题仍然存在：您必须不断修改代码以适应不断增加的存储桶数量。

该困境的解决方案是通过有效模拟嵌套到级别的循环来容纳任意数量N的桶的单一算法。索引数组将代替嵌套语句的循环控制变量：forNNNNfor

// Find all `N`-item combinations consisting 1 item picked from 

// each of an `N` buckets

static <T> List<List<T>> pick1fromN(List<List<T>> s)

{

    List<List<T>> result = new ArrayList<>();

    int[] idx = new int[s.size()];

    while (idx[0] < s.get(0).size()) {

        List<T> pick = new ArrayList(s.size());

        for (int i = 0; i < idx.length; ++i) {

            pick.add(s.get(i).get(idx[i]));

        }

        result.add(pick);

        int i = idx.length - 1;

        while (++idx[i] >= s.get(i).size() && i > 0) {

            idx[i] = 0;

            --i;

        }

    }

    return result;

}

索引都从零开始，每个索引在达到相应存储桶的大小时最大化。要进入下一个组合（内while循环），最后一个索引索引会增加；如果已达到最大值，则将其重置为零，并递增下一个更高的索引。如果下一个更高的索引也最大化，它会重置并导致下一个索引增加，依此类推。 idx[0]递增后永远不会重置，以便外部while可以检测何时idx[0]已达到最大值。

k从每个桶中挑选物品基本上是相同的过程，除了用桶的k 组合集代替原始桶：

// Find all `N * k`-item combinations formed by picking `k` items

// from each of `N` buckets

static <T> List<List<T>> pickKfromEach(List<List<T>> sets, int k)

{

    List<List<List<T>>> kCombos = new ArrayList<>(sets.size());

    for (List<T> ms : sets) {

        kCombos.add(combinations(ms, k));

    }

    ArrayList<List<T>> result = new ArrayList<>();

    int[] indices = new int[kCombos.size()];

    while (indices[0] < kCombos.get(0).size()) {

        List<T> pick = new ArrayList<>(kCombos.size());

        for (int i = 0; i < indices.length; ++i) {

            pick.addAll(kCombos.get(i).get(indices[i]));

        }

        result.add(pick);

        int i = indices.length - 1;

        while (++indices[i] >= kCombos.get(i).size() && i > 0) {

            indices[i] = 0;

            --i;

        }

    }

    return result;

}

static <T> List<List<T>> combinations(List<T> s, int k) throws IllegalArgumentException

{

    if (k < 0 || k > s.size()) {

        throw new IllegalArgumentException("Can't pick " + k

            + " from set of size " + s.size());

    }

    List<List<T>> res = new LinkedList<>();

    if (k > 0) {

        int idx[] = new int[k];

        for (int ix = 0; ix < idx.length; ++ix) {

            idx[ix] = ix;

        }

        while (idx[0] <= s.size() - k) {

            List<T> combo = new ArrayList<>(k);

            for (int ix = 0; ix < idx.length; ++ix) {

                combo.add(s.get(idx[ix]));

            }

            res.add(combo);

            int ix = idx.length - 1;

            while (ix > 0 && (idx[ix] == s.size() - k + ix))

               --ix;

            ++idx[ix];

            while (++ix < idx.length)

                idx[ix] = idx[ix-1]+1;

        }

    }

    return res;

}

与pick 例程一样，该combinations方法使用索引数组来枚举组合。但这些指数的管理方式略有不同。索引从 {0, 1, 2, ..., k -1_} 开始，当它们达到值 { n - k , n - k + 1, ..., n }时它们会最大化。为了进入下一个组合，将最后一个尚未达到最大值的索引递增，然后将每个后续索引重置为其上一个的值加一。

Answer 2

您正在努力解决的问题不能轻易迭代解决，因为复杂性随给定数组的数量而变化。此问题的解决方案是使用递归函数生成第一个参数和所有后续数组的排列。

不幸的是，我现在无法编写任何完全有效的代码，但我可以尝试给您举个例子：

public static Object[] permuteAll(Object[] objs1, Object[][] objs2) {

    if(objs2.length == 1){

        return permuteAll(objs1, objs2);

    }else{

        return permuteAll(objs2[0], objs2[/*The rest of the objs[][]*/]]);

    }

}

public static Object[] permuteAll(Object[] objs1, Object[] objs2) {

    return ... //Your Code for 2 buckets goes here

}

我还建议使用泛型而不是 Object 类，但是根据您组合对象的方式，您可能无法从中获得任何真正的好处......