// Path: src/com/rcwang/seal/util/ComboMaker.java
// public class ComboMaker<T> {
//   
//   public static void main(String args[]) {
//     Set<String> set = new HashSet<String>();
//     set.add("a");
//     set.add("b");
//     set.add("c");
//     set.add("d");
//     
//     ComboMaker<String> comboMaker = new ComboMaker<String>();
//     List<List<String>> comboLists = comboMaker.make(set, 2);
//     for (int i = 0; i < comboLists.size(); i++) {
//       List<String> comboList = comboLists.get(i);
//       System.out.print((i+1) + ". ");
//       for (String s : comboList)
//         System.out.print(s + ", ");
//       System.out.println();
//     }
//   }
//   
//   /**
//    * Generates all possible combinations of size n from the input entities.
//    * The generated list of combinations are in random order.
//    * @param entities the input entities
//    * @param n the size n
//    * @return a list of entity combinations
//    */
//   public List<List<T>> make(Collection<T> entities, int n) {
//     return make(new ArrayList<T>(entities), n);
//   }
// 
//   public List<List<T>> make(List<T> entities, int n) {
//     if (n > entities.size()) return null;
//     List<List<T>> resultList = new ArrayList<List<T>>();
//     int[] arr = null;
// 
//     while (true) {
//       if (arr != null && arr[0] == entities.size()-arr.length)
//         break;
//       if (arr == null) {
//         arr = new int[n];
//         for (int i = 0; i < n; i++)
//           arr[i] = i;
//       } else if (arr[arr.length-1] == entities.size()-1) {
//         for (int i = 0; i < arr.length;i++) {
//           if (arr[i] == entities.size()-arr.length+i) {
//             arr[i-1]++;
//             for (int j = i; j < arr.length; j++)
//               arr[j] = arr[j-1] + 1;
//             break;
//           }
//         }
//       } else arr[arr.length-1]++;
// 
//       List<T> list = new ArrayList<T>();
//       for (int i = 0; i < arr.length ; i++)
//         list.add(entities.get(arr[i]));
//       resultList.add(list);
//     }
//     return resultList;
//   }
// }


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.apache.log4j.Logger;
import com.rcwang.seal.util.ComboMaker;

/**************************************************************************
 * Developed by Language Technologies Institute, Carnegie Mellon University
 * Written by Richard Wang (rcwang#cs,cmu,edu)
 **************************************************************************/
package com.rcwang.seal.expand;




public class RankedComboMaker {

  public static Logger log = Logger.getLogger(RankedComboMaker.class);
  
  public static final int DEFAULT_MAX_COMBINATIONS = 128;
  private ComboMaker<Entity> comboMaker;
  private int maxCombinations;
  
  public static void main(String args[]) {
    int n = 100, k = 1;
    System.out.println(choose(n, k));
    n = getN(k, DEFAULT_MAX_COMBINATIONS);
    System.out.println(n);
    System.out.println(choose(n, k));
  }

  private static long choose(int n, int k) {
    if (n < k) return 0;
    else if (n == k) return 1;
    double answer = 1;
    for (int i = 0; i < k; i++)
      answer *= (double)(n-i)/(k-i);
    return (long) answer;
  }
  
  // returns 'n' such that n choose k <= combo && (n+1) choose k > combo
  private static int getN(int k, int combo) {
    if (k <= 0) {
      log.error("Error: k=" + k + " must be greater than zero, returning -1...");
      return -1;
    }
    for (int n = k+1; ; n++)
      if (choose(n, k) > combo)

// Path: src/com/rcwang/seal/util/ComboMaker.java
// public class ComboMaker<T> {
//   
//   public static void main(String args[]) {
//     Set<String> set = new HashSet<String>();
//     set.add("a");
//     set.add("b");
//     set.add("c");
//     set.add("d");
//     
//     ComboMaker<String> comboMaker = new ComboMaker<String>();
//     List<List<String>> comboLists = comboMaker.make(set, 2);
//     for (int i = 0; i < comboLists.size(); i++) {
//       List<String> comboList = comboLists.get(i);
//       System.out.print((i+1) + ". ");
//       for (String s : comboList)
//         System.out.print(s + ", ");
//       System.out.println();
//     }
//   }
//   
//   /**
//    * Generates all possible combinations of size n from the input entities.
//    * The generated list of combinations are in random order.
//    * @param entities the input entities
//    * @param n the size n
//    * @return a list of entity combinations
//    */
//   public List<List<T>> make(Collection<T> entities, int n) {
//     return make(new ArrayList<T>(entities), n);
//   }
// 
//   public List<List<T>> make(List<T> entities, int n) {
//     if (n > entities.size()) return null;
//     List<List<T>> resultList = new ArrayList<List<T>>();
//     int[] arr = null;
// 
//     while (true) {
//       if (arr != null && arr[0] == entities.size()-arr.length)
//         break;
//       if (arr == null) {
//         arr = new int[n];
//         for (int i = 0; i < n; i++)
//           arr[i] = i;
//       } else if (arr[arr.length-1] == entities.size()-1) {
//         for (int i = 0; i < arr.length;i++) {
//           if (arr[i] == entities.size()-arr.length+i) {
//             arr[i-1]++;
//             for (int j = i; j < arr.length; j++)
//               arr[j] = arr[j-1] + 1;
//             break;
//           }
//         }
//       } else arr[arr.length-1]++;
// 
//       List<T> list = new ArrayList<T>();
//       for (int i = 0; i < arr.length ; i++)
//         list.add(entities.get(arr[i]));
//       resultList.add(list);
//     }
//     return resultList;
//   }
// }


// Path: src/com/rcwang/seal/expand/RankedComboMaker.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.apache.log4j.Logger;
import com.rcwang.seal.util.ComboMaker;

/**************************************************************************
 * Developed by Language Technologies Institute, Carnegie Mellon University
 * Written by Richard Wang (rcwang#cs,cmu,edu)
 **************************************************************************/
package com.rcwang.seal.expand;




public class RankedComboMaker {

  public static Logger log = Logger.getLogger(RankedComboMaker.class);
  
  public static final int DEFAULT_MAX_COMBINATIONS = 128;
  private ComboMaker<Entity> comboMaker;
  private int maxCombinations;
  
  public static void main(String args[]) {
    int n = 100, k = 1;
    System.out.println(choose(n, k));
    n = getN(k, DEFAULT_MAX_COMBINATIONS);
    System.out.println(n);
    System.out.println(choose(n, k));
  }

  private static long choose(int n, int k) {
    if (n < k) return 0;
    else if (n == k) return 1;
    double answer = 1;
    for (int i = 0; i < k; i++)
      answer *= (double)(n-i)/(k-i);
    return (long) answer;
  }
  
  // returns 'n' such that n choose k <= combo && (n+1) choose k > combo
  private static int getN(int k, int combo) {
    if (k <= 0) {
      log.error("Error: k=" + k + " must be greater than zero, returning -1...");
      return -1;
    }
    for (int n = k+1; ; n++)
      if (choose(n, k) > combo)

        return n-1;
