» Beust Sequence Ruminations #

Paul R. Brown @ 2008-07-02

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...


← 2008-06-25 — Getting bash Completion Magic on OS X
→ 2008-07-26 — Local is Just Better