Cédric posted a nice puzzle on his blog:
[W]rite a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.
Bob tweeted
about a minimal solution in
terms of execution time, although (like the guy in the cartoon)
I still like my Haskell version of the sequence (up to some details
with use of Data.Int.Int64 and typing the enumeration):
f k = [ n | n <- [1..k], (length . show $ n) == (length . nub . show $ n) ]
And the function to compute the maximum gap:
drop_tail k = reverse . (drop k) . reverse by_pairs u = zip (drop 1 u) (drop_tail 1 u) g k = maximum . map (uncurry (-)) . by_pairs . f $ k
This approach, while visually appealing, is unacceptably slow, even
with some of the usual optimizations applied. The fact is that any
solution that is implemented in terms of testing all of the numbers
between 0 and k will perform orders of
magnitude more poorly than the recursive style that Bob's using. But
how would I know that...?
Subfactorials, Derangements, and Chooses
A derangement is a permutation with no fixed points, e.g.,
(123) is a derangement of the set {1,2,3},
but (12) is not because it maps 3 to
3. Like the number of permutations of an
n-element set (n!), the number of
derangements has its own function called the subfactorial and written
!n. MathWorld has a decent write-up,
with the major takeaway for present purposes being that !n ~
n!.
The number of elements in Cédric's set, for a fixed radix
n is the sum from k=0 up to n
of !k (n choose k), and that's much smaller than
nn. (This reminds me of the whole "bad
shuffle" meme
from a long time ago.)
Just how much less work does the enumeration approach require than the iteration approach? Here's a quick snippet to compute the number of derangements and the corresponding Beust number for a given radix:
fac :: Integer -> Integer fac 0 = 1 fac n = n * (fac (n-1)) choose :: Integer -> Integer -> Integer choose n k = (fac n) `div` ((fac k) * (fac (n-k))) d :: Integer -> Integer d 1 = 0 d 2 = 1 d n = (n-1) * ( d (n-1) + d (n-2) ) b :: Integer -> Integer b n = sum [ (d k) * (n `choose` k) | k <- [ 1..n ] ]
Then, b10 is 3628799, so a
solution like Bob's should have around a 2500-fold advantage over a
more brute force method. And that advantage gets huge in
short order. As reminder of how much bigger nn
is than n! and friends, 2626 is
roughly 15,264,691,107 times larger than
b26...
