Skip to main content
 首页 » 编程设计

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

2025年12月25日53zengkefu

我有一组选项，我正在尝试动态生成组合以进行测试。我想定义存储桶，并让代码生成所有组合，并通过 @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 传递每个桶的拣选数量。

尽管解决方案代码会受到欢迎，但我更感兴趣的是其背后的推理。

更新 对于 future 的访客，这是凯文·安德森 (Kevin Anderson) 的通用形式的精彩答案:

单元测试:

import static org.testng.Assert.assertEquals; 
 
import java.util.Arrays; 
import java.util.List; 
 
import org.testng.annotations.Test; 
 
public class CombinationNGTest 
{ 
  @Test 
  public void testCombinaitonOnePick() 
  { 
    List<List<Integer>> result 
            = Combination.pickKfromEach((List<List<Integer>>) Arrays.asList( 
                    Arrays.asList(1, 2), 
                    Arrays.asList(3, 4)), 
                    1); 
 
    assertEquals(result.size(), 4, result.toString()); 
 
    result = Combination.pickKfromEach((List<List<Integer>>) Arrays.asList( 
            Arrays.asList(1, 2), 
            Arrays.asList(3, 4), 
            Arrays.asList(5, 6)), 
            1); 
 
    assertEquals(result.size(), 8, result.toString()); 
 
    result = Combination.pickKfromEach((List<List<Integer>>) Arrays.asList( 
            Arrays.asList(1, 2), 
            Arrays.asList(3, 4), 
            Arrays.asList(5, 6), 
            Arrays.asList(7, 8)), 
            1); 
 
    assertEquals(result.size(), 16, result.toString()); 
 
    List<List<String>> result2= Combination.pickKfromEach((List<List<String>>) Arrays.asList( 
                    Arrays.asList("A", "B"), 
                    Arrays.asList("C", "D")), 
                    1); 
 
    assertEquals(result2.size(), 4, result.toString()); 
  } 
 
  @Test 
  public void testCombinaitonMultiplePicks() 
  { 
    List<List<Integer>> result 
            = Combination.pickKfromEach((List<List<Integer>>) Arrays.asList( 
                    Arrays.asList(1, 2, 3), 
                    Arrays.asList(4, 5, 6)), 
                    2); 
 
    assertEquals(result.size(), 9, result.toString()); 
  } 
}

请您参考如下方法:

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

这是一个针对两桶情况的更简单的解决方案，通用并使用 List s 代替数组:

// 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 ，通过有效模拟 for循环嵌套到 N水平。 N 的数组索引将取代N N的循环控制变量嵌套for声明:

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

索引全部从零开始，每个 maxx 在达到相应存储桶的大小时退出。要进入下一个组合(内部 while 循环)，最后一个索引索引会递增；如果已 maxxed，则将其重置为零，并递增下一个较高的索引。如果下一个较高的索引也达到最大值，它将重置并导致下一个索引递增，依此类推。 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; 
}

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


  文章来源：
  https://www.jiuzhua.com/post/fgihga2b6.html
阅读延展