/*
 *  Map integers (1, ...) to combinations of an alphabet
 *  (for example for the alphabet = a .. z) we get:
 *
 *    1    a
 *    2    b
 *    25   y
 *    26   z
 *    27   aa
 *    28   ab
 *    701  yz
 *    702  zz
 *    703  aaa
 *    etc...
 *
 *  NOTE: for the MD5 cracking project you should use something
 *  more SIMPLE. This code is shown just because the question was
 *  asked in the lab.
 *
 */

import java.util.ArrayList;

public class Combinations {

  
  public static void main(String a[]) {

      Combinations c = new Combinations("abcdefghijklmnopqrstuvwxyz");
      System.out.println((1)          + " " + c.getKey(1));
      System.out.println((2)          + " " + c.getKey(2));
      System.out.println((25)         + " " + c.getKey(25));
      System.out.println((26)         + " " + c.getKey(26));
      System.out.println((27)         + " " + c.getKey(27));
      System.out.println((28)         + " " + c.getKey(28));
      System.out.println((26*26+26-1) + " " + c.getKey(26*26+26-1));
      System.out.println((26*26+26)   + " " + c.getKey(26*26+26));
      System.out.println((26*26+26+1) + " " + c.getKey(26*26+26 + 1));
  }


  private ArrayList<Long> bound; 
  private String alphabet;

  /*
   *  constructor:
   *  - store the given alphabet
   *  - build the array "bound" in such a way that 
   *    if an integer is strictly smaller than "bound[j]" it has at most "j" digits
   */

  public Combinations(String alphabet) {
    this.alphabet = alphabet;
    int n = alphabet.length();
    bound = new ArrayList<Long>();
    long poly = 1;
    long power = n;
    while (poly >= 0) {  // until there's overflow
      bound.add(poly);
      poly += power;
      power *= n;
    }
  }

  /*
   * get the "i"-the key starting from i = 1
   */
  private String getKey(long i) {
    // find out key length
    int j;
    for (j = 0; j < bound.size(); j++) {
      if (i < bound.get(j)) {
        break;
      }
    } // => so we know the "i"-th key has "j" digits
    long rest = i; 
    // subtract baseline
    if (j > 0) {
      rest -= bound.get(j - 1);
    }
    // convert the rest to base n 
    long n = alphabet.length();
    String key = "";
    do {
      key += alphabet.charAt((int)(rest % n));
      rest /= n;
    } while (rest > 0);
    // pad the string result with first letter of the alphabet to the left
    while (key.length() < j) {
      key = alphabet.charAt(0) + key;
    }
    // done :)
    return key;    
  }

}