/**
 * Finds base 10 numbers whose digits don't repeat. Solution to Cedric's
 * coding challenge: http://beust.com/weblog/archives/000491.html
 *
 * @author Bob Lee (crazybob@crazybob.org)
 */
public class BeustSequence {

  /**
   * Finds all numbers in sequence up to max.
   *
   * @param max maximum sequence value
   * @param listener hears search results
   */
  public static void findAll(long max, Listener listener) {
    for (int length = 1; length < 11; length++) {
      if (find(1, length, 1, 0, max, listener)) return;
    }
  }

  /**
   * Called recursively for each digit from most to least significant.
   *
   * @param first digit, 0 or 1
   * @param remaining digits
   * @param value so far
   * @param used digit bitfield
   * @param max value
   * @param listener hears results
   * @return true if we reached max, false otherwise
   */
  private static boolean find(int first, int remaining, long value,
      int used, long max, Listener listener) {
    for (int digit = first; digit < 10; digit++, value++) {
      int mask = 1 << digit;
      if ((used & mask) == 0) {
        if (remaining == 1) {
          if (value > max) return true;
          listener.hear(value);
        } else if (find(0, remaining - 1, value * 10, used | mask, max,
            listener)) {
          return true;
        }
      }
    }
    return false;
  }
}