Most optimal way to combine unique groups of size k from n that meet specific requirements

Question

I have been working on something the past few days that seems to be working as intended, however I am looking for ways to improve it. I have a set of n items, and I need to put together groups of these items that MUST meet ALL of the following requirements:

• 2 items from Category A
• 2 items from Category B
• 2 items from Category C
• 2 Items from Category D
• 1 item from Category E

I am currently using the following recursive method to put my groups together and the isValid() method is being used to determine if the group meets the criteria.

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

I am able to see valid results get printed as the program runs, however the original size of items that I am working with can be well over 100 items. This means there is a very large number of total possible groups that will be iterated through and a lot of times the program never actually completes.

I know that there are currently a bunch of wasted iterations, for example if at some point I detect a group is invalid because it has 3 items from Category A, I should be able to move on. I am not sure if my current method with a few tweaks is the best way to go about this, or if I should separate the items into their respective groups first, and then from their put only valid combinations together. Any help would be appreciated. Thanks.

EDIT: I tried to make the method a bit more simpler than my actual method. My actual method takes in an array of Objects that I've created that contain their value along with their category. I guess for the example we can assume that each category is represented by a list of Strings that it contains. The method can be called like:

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

Output:

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

etc...

Answer 1

This seems to work.

I use a BitPattern iterator I wrote a while ago that walks all n-bit numbers containing just k set bits and uses that to select from your categories.

Note that much of this code is building the test data to reflect your requirements.

I hold a List of Iterables which are the BitPatterns. A list of Iterators which are the currently in-use Iterators from the BitPatterns (they must be renewed every time they complete) and a List of BigIntgers that are the current values to explode into selections from the data.

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

This is the BitPattern iterator.

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

  }

}

Answer 2

I will not write code but will list a possible approach. I say possible because it will be running and storing all data in memory and is not the best in regard to algorithms. yet, it is an approach where you don't need to eliminate invalid options. I will use an example in order to make things more clear.

suppose you have categories A,B,C. Where K=2 for A,B and K=1 for C. you also have the input items A1,B1,B2,A2,C1,A3

1- go over the items and divide them according to their category. so you prepare an array/list for each category that has all the items that belong to it.

so now you have arrays:

Category A = [A1,A2,A3] , Category B = [B1,B2] and Category C=[C1]

2- now after preparing the lists, prepare the various legal groups that you can have for picking K items from N items found in that list . here is a link that might help in doing that efficiently: How to iteratively generate k elements subsets from a set of size n in java?

now you have:

first group belonging to category A: [A1,A2] , [A1,A3], [A2,A3] (3 elements)

second group belonging to category B: [B1,B2] (1 element)

third group belonging to category C: [C1] (1 element)

3- now, if you treat each such group as an item, the question transforms to how many different ways are there for picking exactly one element from each group. and that is supposed to be easier to program recursively and will not require eliminating options. and if the number of categories is constant, it will be nested loops over the sets of groups in second point above.

EDIT

the approach works well in eliminating the need to validate bad combinations. yet, there will still be a problem in regard of time. Here is the code that I made to demonstrate. it makes a list of 100 items. then it does the steps mentioned. Note that I commented out the code that prints the groups. The calculation is very fast up to that point. I have added code that prints how many legal choices can be made from each group.

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


    }



}

in a specific run, it gave the following:

A groups number: 210 B groups number: 153 C groups number: 210 D groups number: 210 E groups number: 19

that means , if we had to print all possible choices of a single element (and here an elemnt is an array containing k choices from a category) from each of these, you will have : 210*153*210*210*19 = 26,921,727,000 now listing/printing over 26 billion variations will take time no matter what and I don't see how it will be minimized.

try setting the total items to 20 and uncomment the printing code to see that everything is working correctly. And see if you really need to list the possible combinations. please remember that every combination here is legal and there are no wasted iterations in all the parts of the code. one final note: I did not treat edge cases like when there are no items in a category to complete K. that you can easily put in the code according to the desired behaviour in that case.

Answer 3

So this seems to be a constraint satisfaction problem. So maybe try backtracking? I believe the following works, but plug in your own data to guaranteee.

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

}