过去几天我一直在研究似乎按预期工作的事情,但我正在寻找改进方法.我有一组n项,我需要将这些项目的组合在一起,必须满足以下所有要求：
> A类的2件物品
> B类> 2件
> C类> 2件
> D类的2件物品
> E类别中的1件商品
我目前正在使用以下递归方法将我的组放在一起,并且isValid()方法用于确定组是否符合条件.
void getGroups(String[] arr, int len, int startPosition, String[] result) {
if(len == 0) {
Group group = new Group(Arrays.asList(result));
if(group.isValid()) {
validGroups.add(group);
group.printGroup();
}
return;
}
for(int i = startPosition; i <= arr.length - len; i++) {
result[result.length - len] = arr[i];
getGroups(arr, len - 1, i + 1, result);
}
}
我能够看到有效的结果在程序运行时被打印出来,但是我正在使用的项目的原始大小可以超过100个项目.这意味着有很多可能的组将被迭代,并且很多时候程序从未实际完成.
我知道目前有一堆浪费的迭代,例如,如果在某些时候我检测到一个组是无效的,因为它有来自A类的3个项目,我应该能够继续前进.我不确定我目前使用一些调整的方法是否是解决此问题的最佳方法,或者我是否应该首先将项目分成各自的组,然后再将它们放入有效的组合中.任何帮助,将不胜感激.谢谢.
编辑：我试图让方法比我的实际方法更简单.我的实际方法接受了一个我创建的对象数组,其中包含它们的值以及它们的类别.我想在这个例子中我们可以假设每个类别都由它包含的字符串列表表示.该方法可以被称为：
String[] items = {"test1", "test2", "test3", "test4", "test5", "test6", "test7",
"test8", "test9", "test10", "test11", "test12", "test13",
"test14", "test15", "test16", "test17", "test18"};
getGroups(items, 9, 0, new String[9]);
EDIT2：
List<String> catA = new ArrayList<String>();
catA.add("test1");
catA.add("test2");
catA.add("test3");
catA.add("test4");
List<String> catB = new ArrayList<String>();
catB.add("test5");
catB.add("test6");
catB.add("test7");
catB.add("test8");
List<String> catC = new ArrayList<String>();
catC.add("test9");
catC.add("test10");
catC.add("test11");
catC.add("test12");
List<String> catS = new ArrayList<String>();
catD.add("test13");
catD.add("test14");
catD.add("test15");
catD.add("test16");
List<String> catE = new ArrayList<String>();
catE.add("test17");
catE.add("test18");
输出：
{"test1", "test2", "test5", "test6", "test9", "test10", "test13", "test14", "test17"}
{"test1", "test2", "test5", "test6", "test9", "test10", "test13", "test14", "test18"}
{"test1", "test2", "test5", "test6", "test9", "test10", "test13", "test16", "test17"}
{"test1", "test2", "test5", "test6", "test9", "test10", "test13", "test15", "test17"}
{"test1", "test2", "test5", "test6", "test9", "test10", "test14", "test15", "test17"}
等等…
解决方法:
我不会编写代码,但会列出一种可能的方法.我说可能因为它将运行并将所有数据存储在内存中并且不是最好的算法.然而,这是一种不需要消除无效选项的方法.我将使用一个例子来使事情更清楚.
假设您有类别A,B,C.其中K = 2表示A,B表示K = 1表示C.
您还有输入项A1,B1,B2,A2,C1,A3
1-仔细检查项目并根据类别划分.所以你为每个具有属于它的所有项目的类别准备一个数组/列表.
所以现在你有了数组：
A类= [A1,A2,A3],B类= [B1,B2],C类= [C1]
2-现在准备好清单后,准备各种法律小组,从该清单中找到的N个项目中挑选K个项目.这里有一个链接可能有助于有效地做到这一点：How to iteratively generate k elements subsets from a set of size n in java?
现在你有：
属于A类的第一组：
[A1,A2],[A1,A3],[A2,A3](3个元素)
属于B类的第二组：
[B1,B2](1个元素)
属于C类的第三组：
[C1](1个元素)
3-现在,如果您将每个这样的组视为一个项目,问题将转换为从每个组中选择一个元素的不同方式.这应该更容易递归编程,不需要删除选项.如果类别的数量是常数,它将在上面第二点的组的集合上嵌套循环.
编辑
该方法很好地消除了验证错误组合的需要.
然而,时间问题仍然存在.这是我演示的代码.它列出了100个项目.然后它会完成上述步骤.
请注意,我注释掉了打印组的代码.
到目前为止,计算速度非常快.我添加了代码,用于打印每组可以做出多少合法选择.
package tester;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
/**
*
* @author
*/
public class Tester {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//generate 100 random items belonging to categories
Random rand=new Random();
List<Item> items=new ArrayList<>();
int a=1,b=1,c=1,d=1,e=1;
for (int i=0;i<100;i++){
int randomNumber=rand.nextInt(5)+1;
CATEGORY_TYPE categoryType=null;
int num=0;
switch (randomNumber) {
case 1:
categoryType=CATEGORY_TYPE.A;
num=a++;
break;
case 2:
categoryType=CATEGORY_TYPE.B;
num=b++;
break;
case 3:
categoryType=CATEGORY_TYPE.C;
num=c++;
break;
case 4:
categoryType=CATEGORY_TYPE.D;
num=d++;
break;
case 5:
categoryType=CATEGORY_TYPE.E;
num=e++;
break;
}
String dummyData="Item "+categoryType.toString()+num;
Item item=new Item(dummyData,categoryType);
items.add(item);
}
//arrange the items in lists by category
List<Item> categoryAItemsList=new ArrayList<>();
List<Item> categoryBItemsList=new ArrayList<>();
List<Item> categoryCItemsList=new ArrayList<>();
List<Item> categoryDItemsList=new ArrayList<>();
List<Item> categoryEItemsList=new ArrayList<>();
for (Item item:items){
if (item.getCategoryType()==CATEGORY_TYPE.A)
categoryAItemsList.add(item);
else if (item.getCategoryType()==CATEGORY_TYPE.B)
categoryBItemsList.add(item);
else if (item.getCategoryType()==CATEGORY_TYPE.C)
categoryCItemsList.add(item);
else if (item.getCategoryType()==CATEGORY_TYPE.D)
categoryDItemsList.add(item);
else if (item.getCategoryType()==CATEGORY_TYPE.E)
categoryEItemsList.add(item);
}
//now we want to construct lists of possible groups of choosing from each category
List<Item[]> subsetStoringListA=new ArrayList<>();
List<Item[]> subsetStoringListB=new ArrayList<>();
List<Item[]> subsetStoringListC=new ArrayList<>();
List<Item[]> subsetStoringListD=new ArrayList<>();
List<Item[]> subsetStoringListE=new ArrayList<>();
processSubsets(categoryAItemsList.toArray(new Item[0]),2,subsetStoringListA);
processSubsets(categoryBItemsList.toArray(new Item[0]),2,subsetStoringListB);
processSubsets(categoryCItemsList.toArray(new Item[0]),2,subsetStoringListC);
processSubsets(categoryDItemsList.toArray(new Item[0]),2,subsetStoringListD);
processSubsets(categoryEItemsList.toArray(new Item[0]),1,subsetStoringListE);
System.out.println(" A groups number: "+subsetStoringListA.size());
System.out.println(" B groups number: "+subsetStoringListB.size());
System.out.println(" C groups number: "+subsetStoringListC.size());
System.out.println(" D groups number: "+subsetStoringListD.size());
System.out.println(" E groups number: "+subsetStoringListE.size());
//now we just print all possible combinations of picking a single group from each list.
//the group is an array with valid choices
// for (Item[] subsetA:subsetStoringListA){
// for (Item[] subsetB:subsetStoringListB){
// for (Item[] subsetC:subsetStoringListC){
// for (Item[] subsetD:subsetStoringListD){
// for (Item[] subsetE:subsetStoringListE){
// print(subsetA);
// print(subsetB);
// print(subsetC);
// print(subsetD);
// print(subsetE);
// System.out.println("\n");
// }
//
// }
// }
// }
// }
}
static void print(Item[] arr){
for (Item item:arr)
System.out.print(item.getDumyData()+" ");
}
static void processSubsets(Item[] set, int k,List<Item[]> subsetStoringList) {
Item[] subset = new Item[k];
processLargerSubsets(set, subset, 0, 0,subsetStoringList);
}
static void processLargerSubsets(Item[] set, Item[] subset, int subsetSize, int nextIndex,List<Item[]> subsetStoringList) {
if (subsetSize == subset.length) { //here we have a subset we need to store a copy from it
subsetStoringList.add(Arrays.copyOf(subset, subset.length));
} else {
for (int j = nextIndex; j < set.length; j++) {
subset[subsetSize] = set[j];
processLargerSubsets(set, subset, subsetSize + 1, j + 1,subsetStoringList);
}
}
}
public static enum CATEGORY_TYPE {A,B,C,D,E}
private static class Item{
private CATEGORY_TYPE categoryType;
private String dumyData;
public Item(String dumyData,CATEGORY_TYPE categoryType) {
this.dumyData = dumyData; //maybe bad name but i mean the object can have many other fields etc
this.categoryType = categoryType;
}
/**
* @return the categoryType
*/
public CATEGORY_TYPE getCategoryType() {
return categoryType;
}
/**
* @return the dumyData
*/
public String getDumyData() {
return dumyData;
}
}
}
在特定的运行中,它给出了以下内容：
团体人数：210
B组编号：153
C组编号：210
D组编号：210
E组编号：19
这意味着,如果我们必须打印单个元素的所有可能选择(这里elemnt是一个包含类别中k个选项的数组),则每个元素都有：210 * 153 * 210 * 210 * 19 = 26,921,727,000
现在列出/打印超过260亿的变化将花费时间,无论如何,我不知道它将如何最小化.
尝试将总项目设置为20并取消注释打印代码以查看一切正常.看看你是否真的需要列出可能的组合.请记住,这里的每个组合都是合法的,并且代码的所有部分都没有浪费的迭代.
最后一点：我没有处理边缘情况,比如类别中没有项目来完成K.在这种情况下,你可以根据所需的行为轻松地输入代码.