CodeWars -- Alphabetic Anagrams

Here is problem’s link

Problem

Consider a “word” as any sequence of capital letters A-Z (not limited to just “dictionary words”). For any word with at least two different letters, there are other words composed of the same letters but in a different order (for instance, “STATIONARILY”/“ANTIROYALIST”, which happen to both be dictionary words; for our purposes “AAIILNORSTTY” is also a “word” composed of the same letters as these two).

We can then assign a number to every word, based on where it falls in an alphabetically sorted list of all words made up of the same group of letters. One way to do this would be to generate the entire list of words and find the desired one, but this would be slow if the word is long.

Given a word, return its number. Your function should be able to accept any word $25$ letters or less in length (possibly with some letters repeated), and take no more than $500$ milliseconds to run. To compare, when the solution code runs the $27$ test cases in JS, it takes $101$ms.

For very large words, you’ll run into number precision issues in JS (if the word’s position is greater than $2^{53}$). For the JS tests with large positions, there’s some leeway ($.000000001\%$). If you feel like you’re getting it right for the smaller ranks, and only failing by rounding on the larger, submit a couple more times and see if it takes.

Python, Java and Haskell have arbitrary integer precision, so you must be precise in those languages (unless someone corrects me).

C# is using a long, which may not have the best precision, but the tests are locked so we can’t change it.

Sample

Sample words, with their rank:

1
2
3
4
5
ABAB = 2
AAAB = 1
BAAA = 4
QUESTION = 24572
BOOKKEEPER = 10743

Solution

题目简单来说就是:

给一个单词$w$,将$w$中的字母重排列可以得到新的单词$w’$,所有这样的单词组成有序集$S = \lbrace w’ : w’ = permutation(w)\rbrace$,求$w$在$S$中的位置。

很自然的想法是生成所有的排列,然后排序得到$S​$,再看$w​$的位置。但是排列的数目是阶乘级别的,比指数还要大,不可能真的生成全排列。

但是问题只是问“$S$中比$w$小的有几个”,于是我们只需要构造比$w$小的单词即可。

$$w = w_1w_2\ldots w_n$$

令$A = \lbrace w_1, w_2, \ldots, w_n \rbrace$表示字符的集合,$B = \lbrace w_1,w_2,\ldots , w_n\rbrace$是一个可重集,

构造比$w​$小的单词$v​$,有两种情况:

  1. $v_1 < w_1​$:那么很显然,无论$v_2v_3\ldots v_n​$是怎样的排列,都有$v < w​$,这样的$v​$的个数是

    $$\sum_{a\in A \land a < w_1} permutations(B - \lbrace a\rbrace)$$

  2. $v_1 = w_1$:那么问题就变成了求$w’ = w_2,w_3\ldots w_n$排第几的问题,递归求解

最后还有一个问题,求一个可重集的排列数目。

全排列的数目为$n!$,

对于字符$a\in A$,由于$w$中有$\text{count}(w, a)$个$a$,所以重复计数$\text{count}(w,a)!$倍,

所以可重集的排列数目是:

$$permutations(B) = \frac{n!}{\prod_{a\in A}\text{count}(w,a)}$$

Haskell Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import Data.List

fac :: Int -> Integer
fac n = product [1..(fromIntegral n)]

calPermutation :: String -> Integer
calPermutation s = f1 `div` f2
where f1 = fac (length s)
f2 = product . map (fac . length) . group . sort $ s

calculate :: String -> Integer
calculate [] = 1
calculate s@(a:as) = cal1 s a + calculate as

cal1 :: String -> Char -> Integer
cal1 s a =
let
s' = filter (<a) (nub s)
in
sum . map (\c -> calPermutation (delete c s)) $ s'
------ 本文结束------
0%