我有一組選項池，我正在嘗試動態生成組合以進行測試。我想定義存儲桶并讓代碼生成所有組合以通過@DataProvider 提供給我的 TestNG 測試?，F在我有一些硬編碼的案例，但很明顯這不是維護代碼的最佳方式。我正在努力處理當 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 每個桶的選擇數量。雖然歡迎提供解決方案代碼，但我對它背后的推理更感興趣。
2 回答
不負相思意
TA貢獻1777條經驗 獲得超10個贊
您遇到了一個過于復雜的解決方案，盡管如此，它恰好適用于兩個存儲桶的情況。但是，正如您所發現的，它不會自然地擴展到三個或更多存儲桶。
這是一個更簡單的解決方案，適用于兩個桶的情況，泛型并使用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 }時它們會最大化。為了進入下一個組合，將最后一個尚未達到最大值的索引遞增，然后將每個后續索引重置為其上一個的值加一。
HUWWW
TA貢獻1874條經驗 獲得超12個贊
您正在努力解決的問題不能輕易迭代解決，因為復雜性隨給定數組的數量而變化。此問題的解決方案是使用遞歸函數生成第一個參數和所有后續數組的排列。
不幸的是，我現在無法編寫任何完全有效的代碼，但我可以嘗試給您舉個例子：
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 類，但是根據您組合對象的方式，您可能無法從中獲得任何真正的好處......
添加回答
舉報
0/150
提交
取消