Java:数组组合，每个数组x
我在组中有一个选项池，我正在尝试动态生成组合以用于测试目的。我想定义存储桶，并让代码生成所有的组合，这些组合将通过@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]添加第三个"bucket“将抛出所有内容。
解决方案如下：
[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。
虽然解决方案代码是受欢迎的，但我更感兴趣的是它背后的原因。
面向未来访问者的更新这里是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());
}
}回答 2
Stack Overflow用户
发布于 2018-10-11 11:51:20
您偶然发现了一个过于复杂的解决方案，尽管如此，它恰好适用于两个存储桶的情况。但是，正如您已经发现的，它不会自然地扩展到三个或更多的存储桶。
对于两个存储桶的情况，这里有一个更简单的解决方案，泛化并使用List代替数组：
// 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;
}现在，您有一个外部循环单步执行第一个存储桶的项目，一个中间循环单步执行第二个存储桶的项目，以及一个最内部的循环单步执行第三个存储桶的元素。
但这种方法受到以下事实的限制:所需的循环嵌套深度与要处理的存储桶的数量直接相关:当然，您可以添加第四、第五等级别的循环嵌套来处理四个、五个或更多的存储桶。然而，基本的问题仍然存在:您必须不断修改代码以适应不断增加的存储桶数量。
这个难题的解决方案是一种单一的算法，它通过有效地模拟嵌套到级的for循环来适应任意数量的桶( N )。N索引数组将替换N嵌套for语句的N循环控制变量：
// 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-combinations集合替换了原始存储桶：
// 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}时，它们达到最大值。为了步入下一个组合，还没有达到最大值的最后一个索引被递增，然后后面的每个索引都被重置为它上面的一个加1的值。
Stack Overflow用户
发布于 2018-10-11 06:34:50
你正在努力解决的问题不能很容易地迭代解决，因为复杂性随着给定数组的数量而变化。这个问题的一个解决方案是使用一个递归函数，该函数生成第一个参数和所有后续数组的排列。
不幸的是，我现在还不能写出任何完全有效的代码，但我可以试着给你举个例子：
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类，但根据您组合对象的方式，您可能无法从中获得任何真正的好处……
https://stackoverflow.com/questions/52749329
复制相似问题