过去几天我一直在做一些似乎按预期工作的东西，但是我正在寻找改进它的方法。 我有一组 n 个项目，我需要将这些项目组合在一起，这些项目必须满足以下所有要求：
- 2 件来自 A 类的商品
- B类2件商品
- C类2件商品
- 2 D类商品
- 类别 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 个项目。 这意味着有大量的可能组将被迭代，并且很多时候程序从未真正完成。
我知道目前有一堆浪费的迭代，例如，如果在某个时候我检测到一个组无效，因为它有 3 个来自类别 A 的项目，我应该能够继续前进。 我不确定我目前的方法是否经过一些调整是解决此问题的最佳方法，或者我是否应该先将项目分成各自的组，然后再将它们仅将有效的组合放在一起。 任何帮助将不胜感激。 谢谢。
编辑：我试图使该方法比我的实际方法更简单一些。 我的实际方法采用我创建的一组对象，其中包含它们的值及其类别。 我想对于示例，我们可以假设每个类别都由它包含的字符串列表表示。 该方法可以像这样调用：
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]);
编辑2：
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"}等。。。
这
似乎有效。
我使用我不久前编写的BitPattern迭代器，它遍历所有仅包含 k 个集合位的 n 位数字，并使用它来从您的类别中进行选择。
请注意，此代码的大部分内容都是构建测试数据以反映您的要求。
我拿着Iterable的List，这是BitPattern s。Iterator的列表，这些是当前正在使用的BitPattern中的Iterator（每次完成时都必须更新），以及List的BigIntger，这些值是要分解为数据选择的当前值。
public class Test {
enum Category {
A(2), B(2), C(2), D(2), E(1);
public final int required;
Category(int required) {
this.required = required;
}
}
private static final Category[] categories = Category.values();
static class Categorised {
final String name;
final Category category;
Categorised(String name, Category category) {
this.name = name;
this.category = category;
}
@Override
public String toString() {
return category.name() + ":" + name;
}
}
static final List<Categorised> data = new ArrayList<>();
static {
data.add(new Categorised("A-1", Category.A));
data.add(new Categorised("A-2", Category.A));
data.add(new Categorised("A-3", Category.A));
data.add(new Categorised("B-1", Category.B));
data.add(new Categorised("B-2", Category.B));
data.add(new Categorised("B-3", Category.B));
data.add(new Categorised("C-1", Category.C));
data.add(new Categorised("C-2", Category.C));
data.add(new Categorised("C-3", Category.C));
data.add(new Categorised("D-1", Category.D));
data.add(new Categorised("D-2", Category.D));
data.add(new Categorised("D-3", Category.D));
data.add(new Categorised("E-1", Category.E));
data.add(new Categorised("E-2", Category.E));
data.add(new Categorised("E-3", Category.E));
}
// Categorise the data.
private Map<Category, List<Categorised>> categorise(List<Categorised> data) {
Map<Category, List<Categorised>> categorised = new EnumMap<>(Category.class);
for (Categorised d : data) {
List<Categorised> existing = categorised.get(d.category);
if (existing == null) {
existing = new ArrayList<>();
categorised.put(d.category, existing);
}
existing.add(d);
}
return categorised;
}
public void test() {
// Categorise the data.
Map<Category, List<Categorised>> categorised = categorise(data);
// Build my lists.
// A source of Iteratprs.
List<BitPattern> is = new ArrayList<>(categories.length);
// The Iterators.
List<Iterator<BigInteger>> its = new ArrayList<>(categories.length);
// The current it patterns to use to select.
List<BigInteger> next = new ArrayList<>(categories.length);
for (Category c : categories) {
int k = c.required;
List<Categorised> from = categorised.get(c);
// ToDo - Make sure there are enough.
int n = from.size();
// Make my iterable.
BitPattern p = new BitPattern(k, n);
is.add(p);
// Gather an Iterator.
Iterator<BigInteger> it = p.iterator();
// Store it.
its.add(it);
// Prime it.
next.add(it.next());
}
// Walk the lists.
boolean stepped;
do {
// Interpret the current numbers.
List<Categorised> candidates = new ArrayList<>();
for ( int c = 0; c < categories.length; c++ ) {
BigInteger b = next.get(c);
List<Categorised> category = categorised.get(categories[c]);
// Step through the bits in the number.
BitSet bs = BitSet.valueOf(b.toByteArray());
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
// Pull those entries from the categorised list.
candidates.add(category.get(i));
}
}
// Print it for now.
System.out.println(candidates);
// Step again.
stepped = step(is, its, next);
} while (stepped);
}
// Take one step.
private boolean step(List<BitPattern> is, List<Iterator<BigInteger>> its, List<BigInteger> next) {
boolean stepped = false;
// Step each one until we make one successful step.
for (int i = 0; i < is.size() && !stepped; i++) {
Iterator<BigInteger> it = its.get(i);
if (it.hasNext()) {
// Done here!
stepped = true;
} else {
// Exhausted - Reset it.
its.set(i, it = is.get(i).iterator());
}
// Pull that one.
next.set(i, it.next());
}
return stepped;
}
public static void main(String args[]) {
new Test().test();
}
}
这是BitPattern迭代器。
/**
* Iterates all bit patterns containing the specified number of bits.
*
* See "Compute the lexicographically next bit permutation"
* http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
*
* @author OldCurmudgeon
*/
public class BitPattern implements Iterable<BigInteger> {
// Useful stuff.
private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = ONE.add(ONE);
// How many bits to work with.
private final int bits;
// Value to stop at. 2^max_bits.
private final BigInteger stop;
// Should we invert the output.
private final boolean not;
// All patterns of that many bits up to the specified number of bits - invberting if required.
public BitPattern(int bits, int max, boolean not) {
this.bits = bits;
this.stop = TWO.pow(max);
this.not = not;
}
// All patterns of that many bits up to the specified number of bits.
public BitPattern(int bits, int max) {
this(bits, max, false);
}
@Override
public Iterator<BigInteger> iterator() {
return new BitPatternIterator();
}
/*
* From the link:
*
* Suppose we have a pattern of N bits set to 1 in an integer and
* we want the next permutation of N 1 bits in a lexicographical sense.
*
* For example, if N is 3 and the bit pattern is 00010011, the next patterns would be
* 00010101, 00010110, 00011001,
* 00011010, 00011100, 00100011,
* and so forth.
*
* The following is a fast way to compute the next permutation.
*/
private class BitPatternIterator implements Iterator<BigInteger> {
// Next to deliver - initially 2^n - 1
BigInteger next = TWO.pow(bits).subtract(ONE);
// The last one we delivered.
BigInteger last;
@Override
public boolean hasNext() {
if (next == null) {
// Next one!
// t gets v's least significant 0 bits set to 1
// unsigned int t = v | (v - 1);
BigInteger t = last.or(last.subtract(BigInteger.ONE));
// Silly optimisation.
BigInteger notT = t.not();
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
// w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
// The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros.
next = t.add(ONE).or(notT.and(notT.negate()).subtract(ONE).shiftRight(last.getLowestSetBit() + 1));
if (next.compareTo(stop) >= 0) {
// Dont go there.
next = null;
}
}
return next != null;
}
@Override
public BigInteger next() {
last = hasNext() ? next : null;
next = null;
return not ? last.not(): last;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not supported.");
}
@Override
public String toString () {
return next != null ? next.toString(2) : last != null ? last.toString(2): "";
}
}
}
我不会写代码，但会列出一种可能的方法。我说可能，因为它将运行并将所有数据存储在内存中，并且在算法方面不是最好的。然而，这是一种不需要消除无效选项的方法。我将使用一个例子，以使事情更加清晰。
假设您有类别 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项。 这里有一个链接可能有助于有效地做到这一点： 如何在 java 中从一组大小为 n 的集合迭代生成 k 个元素子集？
现在您有：
属于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;
}
}
}
在特定运行中，它给出了以下内容：
团体人数：210B组人数：153C组人数：210D组人数：210E组人数：19
这意味着，如果我们必须从每个元素中打印单个元素的所有可能选项（这里 elemnt 是一个包含类别中的 k 个选项的数组），您将得到：210*153*210*210*19 = 26,921,727,000现在列出/打印超过 260 亿个变体无论如何都需要时间，而且我看不出如何将其最小化。
尝试将"总项目数"设置为 20 并取消注释打印代码以查看一切是否正常工作。看看你是否真的需要列出可能的组合。请记住，这里的每个组合都是合法的，并且在代码的所有部分都没有浪费迭代。最后一点：我没有处理边缘情况，例如当类别中没有项目可以完成 K 时，您可以根据在这种情况下的所需行为轻松放入代码。
所以这似乎是一个约束满足问题。所以也许尝试回溯？我相信以下有效，但插入您自己的数据以保证。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Launch {
public static void main(String[] args) {
// Formulate the constraints.
int[] constraints = { 2, 1, 0, 1 };
// Create all the items.
List<boolean[]> items = new ArrayList<boolean[]>();
boolean[] i1 = { true, false, true, false };
boolean[] i2 = { true, false, false, false };
boolean[] i3 = { false, true, false, true };
boolean[] i4 = { false, false, false, true };
items.add(i1);
items.add(i2);
items.add(i3);
items.add(i4);
// Solve!
backtrack(constraints, items);
}
/**
* Recursively generate possible solutions but backtrack as soon as the constraints fail.
*/
private static void backtrack(int[] constraints, List<boolean[]> items) {
// We start with no items belonging to any categories.
List<List<boolean[]>> memberships = new ArrayList<List<boolean[]>>();
for (int i = 0; i < constraints.length; i++) {
memberships.add(new ArrayList<boolean[]>());
}
backtrack(constraints, items, memberships);
}
/**
* Recursively generate possible solutions but backtrack as soon as the constraints fail.
*/
private static void backtrack(int[] constraints, List<boolean[]> items,
List<List<boolean[]>> memberships) {
if (items.isEmpty() && !acceptable(constraints, memberships)) {
return;
} else if (acceptable(constraints, memberships)) {
display(memberships);
} else {
for (boolean[] item : items) {
int catIdx = 0;
for (boolean belongs : item) {
if (belongs) {
// The item and category were chosen so let's update
// memberships.
List<List<boolean[]>> newMemberships = new ArrayList<List<boolean[]>>();
for (List<boolean[]> old : memberships) {
newMemberships.add(new ArrayList<boolean[]>(old));
}
newMemberships.get(catIdx).add(item);
// We've placed the item so let's remove it from the
// possibilities.
List<boolean[]> newItems = new ArrayList<boolean[]>(
items);
newItems.remove(item);
// Now solve the sub-problem.
backtrack(constraints, newItems, newMemberships);
}
catIdx++;
}
}
}
}
/**
* A nice way to display the membership tables.
*/
private static void display(List<List<boolean[]>> memberships) {
System.out.println("---");
for (List<boolean[]> category : memberships) {
for (boolean[] item : category) {
System.out.print(Arrays.toString(item) + " ");
}
System.out.println();
}
}
/**
* Returns whether or not a list of memberships are accepted by the
* constraints.
*
* @param constraints
* - The number of items required per category.
* @param memberships
* - The current items per category.
*/
private static boolean acceptable(int[] constraints,
List<List<boolean[]>> memberships) {
boolean acceptable = memberships.size() == constraints.length;
for (int i = 0; i < memberships.size(); i++) {
acceptable = acceptable
&& constraints[i] == memberships.get(i).size();
}
return acceptable;
}
}