计算词典排名

Question

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

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

输入

• 字符集：

  A,B,C

• 输入：

  BAA

  （注意

  C

  不包括在输入中）
• 长度：

  3

  （字符组合的最大长度...还必须包括 1 和 2 个字符组合）

输出

• 16

注意事项

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

所有组合（按顺序）

1. A
2. AA
3. AAA
4. AAB
5. AAC
6. AB
7. 阿巴
8. ABB
9. ABC
10. 空调
11. ACA
12. ACB
13. ACC
14. 乙
15. 巴
16. BAA
17. 巴布
18. BAC
19. BB
20. BBA
21. BB
22. 英国广播公司
23. 公元前
24. BCA
25. BCB
26. 密件抄送
27. C
28. CA
29. 民航局
30. 驾驶室
31. CAC
32. CB
33. CBA
34. CBB
35. 加拿大广播公司
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