最優化的方式來組合n個大小爲k的特殊組，以滿足特定要求

Question

我一直在研究過去幾天似乎按預期工作的內容，但是我正在尋找改進方法。我有一組n個項目，我需要放在一起，這些項目組必須滿足所有的下列要求：

• 2項從類別從類別B A
• 2項
• 2從C類物品從類別d
• 2個項目
• 1從E類項我目前使用以下遞歸方法把米

y組合在一起並且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]); 

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

等等

Answer 1

我不會寫代碼，但會列出一個可能的方法。我說是可能的，因爲它將運行並將所有數據存儲在內存中，而對於算法來說並不是最好的。然而，這是一種不需要消除無效選項的方法。爲了使事情更清楚，我會用一個例子。

假設您有類別A，B，C。對於A，B和K = 1，K = 2。 您還可以輸入項目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; 
     } 


    } 



} 

在特定運行

，它給出以下：

A基團數：210 B兩組數：153 C三組數：210個 d基團數：210個 È組數：19

這意味着，如果我們必須打印所有可能的單個元素的選擇（這裏elemnt是包含來自某個類別的k個選項的數組），則您將擁有：210 * 153 * 210 * 210 * 19 = 26,921,727,000 現在上市/打印結束無論如何，有260億變化需要時間，我不知道如何將其最小化。

嘗試將總項目設置爲20並取消註釋打印代碼以查看所有內容都正常工作。看看你是否真的需要列出可能的組合。請記住，這裏的每個組合都是合法的，代碼的所有部分都沒有浪費迭代。 最後一個注意事項：我沒有處理邊緣案例，比如某個類別中沒有任何項目要完成K.您可以根據所需的行爲輕鬆地放入代碼。

Answer 2

因此，這似乎是一個constraint satisfaction problem。所以也許試試backtracking？ 我相信下面的工作，但插入自己的數據保證。

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 3

這似乎工作。

我使用了一個BitPattern迭代器，我前一段時間寫過遍歷所有包含k個集合位的n位數字，並用它從您的類別中進行選擇。

請注意，此代碼的大部分內容都是構建測試數據以反映您的要求。

我持有List的Iterable這是BitPattern s。當前正在使用的Iterator s的列表，其中BitPattern s（它們必須在每次完成時更新）和List的BigIntger s，它們是從數據中選擇的當前值。

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

    } 

}