Cedric's coding challenge

Although I came late to the party at Cedric's coding challenge, this is the kind of problem I just can't resist taking at least a little dip into. The idea is to generate all numbers up to a maximum that do not have any repeated digits.

My initial thought was that the pattern of digits for an n-digit number should be the same, you just need to recode the values. I.e. given 3 digits a, b and c from which you should generate all 3-digit sequences without repeated digits, then generating the 2-digit suffixes ac and ca after choosing b as the first digit is the same as choosing a as the first digit, generating bc and cb and then recoding a->b, b->a and c->c.

Anyway, I soon realized that I couldn't come up with an efficient recoding algorithm and also that generating the suffixes didn't cost much more than an iteration over a pre-generated suffix list. So I basically ended up with the same algorithm as crazybob and Jonathan Hawkes improvement. Happily, my implementation was a bit faster still than both of theirs, 30% faster than Bob's and 20% faster than Jonathan's in Bob's way of counting and when measured like Jonathn does it, mine is 65% faster than Bob's and 30% faster than Jonathan's. Here it is:

/** 
 * Finds base 10 numbers whose digits don't repeat. Solution to Cedric's coding 
 * challenge: http://beust.com/weblog/archives/000491.html 
 * 
 * @author Torbjorn Gannholm 
 */ 
public class NonRepeatingDigits { 
  private final long max; 
  private final int base; 
  private final Listener listener; 
  private final Digit head; 
 
  /** 
   * Finds all numbers with non-repeating digits in the supplied base up to max. 
   * @param base The base, e.g. octal (8), decimal (10), hexadecimal (16). 
   * @param max Upper bound for returned values. 
   * @param listener Listener to receive valid numbers. 
   */ 
  public NonRepeatingDigits(int base, long max, Listener listener) { 
    this.base = base; 
    this.max = max; 
    this.listener = listener; 
    head = new Digit(base); 
  } 
 
  public void run() { 
    // One digit numbers. 
    for (Digit current = head.next.next; 
         current != null; 
         current = current.next) { 
      int value = current.value; 
      if (value > max) return; 
      listener.hear(value); 
    } 
    // Pick first digit (non-zero), then find the rest of the number. 
    for (int digitsAfterFirst = 1; 
         digitsAfterFirst < base; 
         digitsAfterFirst++) { 
      for (Digit previous = head.next, current = head.next.next; 
          current != null; 
          // Restore removed digit to sequence. 
          previous.next = current, previous = current, current = current.next) { 
        // Remove chosen digit from sequence. 
        previous.next = current.next; 
        if (followingDigits(digitsAfterFirst, current.value * base)) return; 
      } 
    } 
  } 
 
  /** A digit, part of a linked list of all digits in a base. 
   * (Shamelessly paraphrased from crazybob) */ 
  private static class Digit { 
    private Digit next; 
    private final int value; 
 
    /** Constructs a non-digit that acts as the head for the list, and the 
     * digits in the list. */ 
    Digit(int base) { 
      value = -1; 
      next = new Digit(base, 0); 
    } 
     
    /** Constructs the real sequence of digits */ 
    private Digit(int base, int value) { 
      this.value = value; 
      if (++value < base) { 
        next = new Digit(base, value); 
      } 
    } 
  } 
 
  /** 
   * Recursively generates digits after the first of a valid number. 
   * @param remaining Number of digits left to generate. 
   * @param prefixValue Value of previous digits. 
   * @return true when values generated are greater than max. 
   */ 
  private boolean followingDigits(int remaining, int prefixValue) { 
    if (remaining > 1) { 
      for (Digit prev = head , current = head.next; 
           current != null; 
           // Restore removed digit to sequence. 
           prev.next = current, prev = current, current = current.next) { 
        // Remove chosen digit from allowable digits. 
        prev.next = current.next; 
        if(followingDigits(remaining - 1, 
                           (prefixValue + current.value) * base)) return true; 
      } 
    } else { 
      for (Digit current = head.next; current != null; current = current.next) { 
        int value = prefixValue + current.value; 
        if (value > max) return true; 
        listener.hear(value); 
      } 
    } 
    return false; 
  } 
}