我有一组选项，我正在尝试动态生成组合以进行测试。我想定义存储桶，并让代码生成所有组合，并通过 @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}。要进入下一个组合，最后一个尚未达到最大值的索引会递增，然后每个后续索引都将重置为其上方索引的值加一。
关于Java:数组的组合，每个数组 x，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52749329/