algorithm - 计算词典排名

Question

我正在尝试计算具有重复字符的给定排列的词典排名。

我发现的所有示例似乎都是针对输入字符串的字谜词(与任意字符集相对)查找给定输入字符串的词典排名

输入

• 字符集:A,B,C
• 输入:BAA(注意输入中不包含C)
• 长度:3(字符组合的最大长度...还必须包括 1 和 2 个字符组合)

输出

• 16

注释

• 可以有重复的字符
• 共有 39 种组合(1、2 或 3 个字符的排列)
• 无法通过生成所有组合等进行暴力破解，因为实际用例涉及更大的字符集/最大字符串长度

所有组合(按顺序)

1. 一个
2. AA
3. AAA
4. AAB
5. AAC
6. AB
7. ABA
8. ABB
9. ABC
10. 交流
11. ACA
12. ACB
13. ACC
14. B
15. 文学士
16. BAA
17. 巴布
18. BAC
19. BB
20. 工商管理学士
21. BBB
22. 英国广播公司
23. 公元前
24. BCA
25. BCB
26. 密件抄送
27. C
28. CA
29. CAA
30. CAB
31. CAC
32. CB
33. CBA
34. CBB
35. CBC
36. 抄送
37. CCA
38. 建行
39. CCC

Answer 1

这看起来基本上就像所有其他排名/取消排名算法对一样，那么做起来比说起来容易吗？简短的版本是，为了获得长度最多为 n 的单词，我们要么先有空单词，要么先有一个字母，后跟一个长度最多为 n−1 的单词。通过从排名中减去一个并除以回答后一个描述的单词数，我们可以得到第一个字母，然后递归(但使用迭代而不是实际递归)。

import itertools


def count_words(alphabet, max_length):
    count = 1
    for i in range(max_length):
        count = count * len(alphabet) + 1
    return count


def word_from_rank(alphabet, rank, max_length):
    count = count_words(alphabet, max_length)
    letters = []
    while rank > 0:
        count = (count - 1) // len(alphabet)
        i, rank = divmod(rank - 1, count)
        letters.append(alphabet[i])
    return "".join(letters)


def rank_from_word(alphabet, word, max_length):
    letter_to_rank = {letter: i for (i, letter) in enumerate(alphabet)}
    count = count_words(alphabet, max_length)
    rank = 0
    for letter in word:
        count = (count - 1) // len(alphabet)
        rank += count * letter_to_rank[letter] + 1
    return rank


def test(alphabet, max_length):
    words = sorted(
        {
            "".join(letters)
            for n in range(max_length + 1)
            for letters in itertools.product(alphabet, repeat=n)
        }
    )
    assert count_words(alphabet, max_length) == len(words)
    for rank, word in enumerate(words):
        assert word_from_rank(alphabet, rank, max_length) == word
        assert rank_from_word(alphabet, word, max_length) == rank


test("ABC", 3)
test("ABCD", 3)
test("ABCDE", 4)
print(rank_from_word("ABC", "BAA", 3))
for i in range(count_words("ABC", 3)):
    print(i, word_from_rank("ABC", i, 3))

输出:

16
0 
1 A
2 AA
3 AAA
4 AAB
5 AAC
6 AB
7 ABA
8 ABB
9 ABC
10 AC
11 ACA
12 ACB
13 ACC
14 B
15 BA
16 BAA
17 BAB
18 BAC
19 BB
20 BBA
21 BBB
22 BBC
23 BC
24 BCA
25 BCB
26 BCC
27 C
28 CA
29 CAA
30 CAB
31 CAC
32 CB
33 CBA
34 CBB
35 CBC
36 CC
37 CCA
38 CCB
39 CCC