含重复字符的Lexicographic Rank计算技术问询

我正在尝试计算含重复字符的给定字符串在任意字符集下的字典序排名。目前找到的示例都是针对输入字符串的变位词求解字典序排名，并不适用于这种基于任意字符集、包含所有1到指定最大长度组合的场景。

输入 #

• 字符集：A,B,C
• 输入字符串：BAA（注意输入中不含C）
• 最大长度：3（需包含长度为1、2、3的所有字符组合）

输出 #

• 排名结果：16

说明 #

• 允许字符重复出现
• 所有符合要求的组合共39种（涵盖1、2、3字符的排列）
• 实际场景会涉及更大的字符集和更长的最大字符串长度，因此不能采用生成所有组合的暴力方法求解

所有有序组合（按字典序排列） #

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

内容的提问来源于stack exchange，提问作者SoonGuy