计算词典排名

Question

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

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

输入

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

输出

• 16

笔记

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

所有组合（按顺序）

1. A
2. AA
3. AAA
4. AAB
5. 亚克力
6. AB
7. ABA
8. ABB
9. ABC
10. 交流电
11. ACA
12. ACB
13. ACC
14. 乙
15. 学士
16. BAA
17. 巴布
18. 巴克
19. BB
20. BBA
21. 血脑屏障
22. 英国广播公司
23. 公元前
24. BCA
25. BCB
26. 密件抄送
27. C
28. CA
29. 中国航空协会
30. 出租车
31. CAC
32. CB
33. 篮球协会
34. 商业银行
35. 加拿大广播公司
36. 抄送
37. CCA
38. 建行
39. CCC

Answer 1

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

\n

import itertools\n\n\ndef count_words(alphabet, max_length):\n    count = 1\n    for i in range(max_length):\n        count = count * len(alphabet) + 1\n    return count\n\n\ndef word_from_rank(alphabet, rank, max_length):\n    count = count_words(alphabet, max_length)\n    letters = []\n    while rank > 0:\n        count = (count - 1) // len(alphabet)\n        i, rank = divmod(rank - 1, count)\n        letters.append(alphabet[i])\n    return "".join(letters)\n\n\ndef rank_from_word(alphabet, word, max_length):\n    letter_to_rank = {letter: i for (i, letter) in enumerate(alphabet)}\n    count = count_words(alphabet, max_length)\n    rank = 0\n    for letter in word:\n        count = (count - 1) // len(alphabet)\n        rank += count * letter_to_rank[letter] + 1\n    return rank\n\n\ndef test(alphabet, max_length):\n    words = sorted(\n        {\n            "".join(letters)\n            for n in range(max_length + 1)\n            for letters in itertools.product(alphabet, repeat=n)\n        }\n    )\n    assert count_words(alphabet, max_length) == len(words)\n    for rank, word in enumerate(words):\n        assert word_from_rank(alphabet, rank, max_length) == word\n        assert rank_from_word(alphabet, word, max_length) == rank\n\n\ntest("ABC", 3)\ntest("ABCD", 3)\ntest("ABCDE", 4)\nprint(rank_from_word("ABC", "BAA", 3))\nfor i in range(count_words("ABC", 3)):\n    print(i, word_from_rank("ABC", i, 3))\n

\n

输出：

\n

16\n0 \n1 A\n2 AA\n3 AAA\n4 AAB\n5 AAC\n6 AB\n7 ABA\n8 ABB\n9 ABC\n10 AC\n11 ACA\n12 ACB\n13 ACC\n14 B\n15 BA\n16 BAA\n17 BAB\n18 BAC\n19 BB\n20 BBA\n21 BBB\n22 BBC\n23 BC\n24 BCA\n25 BCB\n26 BCC\n27 C\n28 CA\n29 CAA\n30 CAB\n31 CAC\n32 CB\n33 CBA\n34 CBB\n35 CBC\n36 CC\n37 CCA\n38 CCB\n39 CCC\n

\n