This was a fun exercise. Once I understood the relationship between similar numbers and the permutations of a number with respect to the repeated digits it contains, the whole thing started making sense.
An n-digit number has n! permutations. Some values will not be unique. Consider the number 112. It has 3 digits, so 6 permutations. Due to the repetition of the digit 1, we get the same numbers twice:
112
112
121
121
211
211
In fact, there are three unique numbers in this permutation: 112, 121, and 211. We need to divide the total number of permutations by the number of possible permutations of the repeated digits.
similarities(n) = length(n)! / sum [ x! | x ∈ repeatedDigits(n) ]
Of course if there are no repeated digits, the number of similar numbers will always be equal to the number of possible permutations of n.
In Haskell-talk (because I live beyond the rules!):
similarities :: Int -> Int
similarities n = (factorial $ length ds) `div` sumOr1 duplicateFactorials
where ds = digits n
repeated (_, y) = y > 1
duplicates = map snd $ filter repeated $ frequencies $ ds
duplicateFactorials = map factorial duplicates
sumOr1 xs = case sum xs of
0 -> 1
s -> s
In order to compute
ds we use the
digits function which turns the number into a list of digits by first converting it into a string and then reading each digit back individually. It's a dirty trick:
digits :: Int -> [Int]
digits x = map (read . (: [])) $ show x
In order to detect repeated digits we find the frequencies of occurence of each digit in
ds by building up an association list (I'm too lazy to use a map). For
1213, the list looks something like
[(2, 1), (1, 2), (3, 1)]. We compute this with the
frequencies function:
frequencies :: Eq a => [a] -> [(a, Int)]
frequencies = foldr frequency []
where frequency x zs =
case lookup x zs of
Just n -> update x (n + 1) zs
Nothing -> (x, 1) : zs
frequencies scans a list of numbers and tries to lookup each number in an association list, if it can't find the number it adds it to the list with a frequency of 1, otherwise it tries to update the association list by incrementing the frequency for that number. The
lookup function is built-in, the
update function is pretty simple, can you think of an implementation?
Once we have the list of frequencies of digits in the number, we filter the list to only keep the frequencies of the digits that have been repeated, and we extract those into a new list called
duplicates. We compute their factorials by mapping the
factorial function over them. I used a lame recursive factorial, but you can use a faster implementation.
Finally we
sum the factorials of the duplicate numbers. If there are no duplicates, this sum will be 0, and since we don't like to divide by 0, we'll just replace it with 1 so that the result of the division is just equal to the number of possible permutations.
