组合满足特定要求的 n 大小 k 的独特组的最优化方法

Question

在过去的几天里，我一直在做一些事情，看起来像预期的那样，但是我在寻找改进的方法。我有一组n个项目，我需要将这些项目组合在一起，这些项目必须满足以下所有要求:

• A类2件
• 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类项目，我应该能够继续前进。我不确定我目前的方法是否是最好的方法，或者我是否应该先将项目分成各自的组，然后从它们的有效组合中分离出来。任何帮助都将不胜感激。谢谢。

编辑：我试图使这个方法比我实际的方法简单一些。我的实际方法接受我创建的一个Objects数组，其中包含它们的值和类别。我想对于这个例子，我们可以假设每个类别都由它包含的String列表表示。该方法可以这样调用：

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"}

等…

Answer 1

所以这似乎是一个约束满足问题。所以也许可以尝试回溯？我相信下面的方法是有效的，但是插入你自己的数据来保证。

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;
    }

}

Answer 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个元素）

现在，如果你把每个这样的组看作一个项目，问题就变成了有多少种不同的方法从每个组中挑选一个元素。这应该更容易递归编程，并且不需要删除选项。如果类别的数量是常数，那么它将在上面第二点中的组集合上嵌套循环。

编辑

该方法在消除验证不良组合的需要方面效果很好。然而，在时间方面仍然存在问题。下面是我为演示而编写的代码。它列出了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;
        }


    }



}

在特定运行中，它给出了以下内容：

A组数：210 B组数：153 C组数：210 D组数：210 E组数：19

这意味着，如果我们必须打印每个元素中单个元素的所有可能选择(这里element是一个包含类别中k个选择的数组),您将得到:210*153*210*210*19 = 26，921，727，000现在列出/打印超过260亿个变化无论如何都需要时间，而且我看不出它将如何被最小化。

尝试将项目总数设置为20，并取消注释打印代码，以查看一切正常工作。看看您是否真的需要列出可能的组合。请记住，这里的每个组合都是合法的，并且代码的所有部分都没有浪费迭代。最后一点注意：我没有处理边缘情况，例如类别中没有要完成K的项目，在这种情况下，您可以根据所需的行为轻松地将其放入代码中。

Answer 3

这似乎行得通。

我使用了一个我不久前写的< code>BitPattern迭代器，它遍历所有仅包含k个集合位的n位数字，并使用它从您的类别中进行选择。

请注意，此代码的大部分内容都在构建测试数据以反映您的需求。

我持有一个< code > iteratable 的< code>List,它们是< code>BitPattern的< code>Iterator的列表，它们是来自< code>BitPattern的当前正在使用的< code>Iterator(它们必须在每次完成时更新),以及一个< code > biginger 的< code>List,它们是要展开成数据选择的当前值。

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): "";
    }

  }

}