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;

}

}

## No comments:

Post a Comment