Math - 查找两个字符串之间的排列数

Question

这不是家庭作业=）。我在做一个项目，它会自动生成顺序计算机名称列表，如果列表将会是一个疯狂的长列表，我想添加一个警告。

我知道如何找到比如说A-ZZZ排列的数目，但我有一个时间赫克尝试应用的容斥集。这里是场景，为了简单起见，字符集只会是A - Z，不区分大小写，所以“A”=“a”。

用户输入“ABC”到“AX”的范围。所以我需要的唯一数字就是在这两者之间。所以psudo逻辑会得到A - ZZZ的全部总数，那么我需要排除，“ABC”之前的所有内容以及“AX”之后的所有内容。

所以现在的问题是，我该如何“ABC”之前和“AX”后发现计数。我查看了所有我的旧版离散和统计数学书，但没有什么适合的，或者在插入数字（n！/ n1！* n2！...）时给我正确的答案。我甚至试图做一些转换二进制或十六进制到十进制，但你知道这是一个史诗般的失败=）。

谢谢，

戴夫

Answer 1

的最简单的解决方案是考虑两个字符串为数字在碱-26表示：

ABC = 26^2 * 0 + 26^1 * 1 + 26^0 * 2 = 28(base 10) 
ACC = 26^2 * 0 + 26^1 * 2 + 26^0 * 2 = 54(base 10) 

ACC - ABC = 54 - 28 = 26 

因此，有在所述范围内的总27串是[ABC, ACC]。

的基本思想是使用positional numeral system与基部26（从A的所有字母 - Z）。

这种方法只有一个问题：
它不能处理空白字符，因为它们不能遵循“默认” - 行为，因为它们只能显示为前缀。

一种解决这一问题将是从

A = 0, B = 1, ..., Z = 25 

扩大值映射到

empty = -1, A = 0, ..., Z = 25 

虽然这打破了数字系统的定义，我们现在能够处理较短的字符串也是如此：

magnitude([ZZ, AAA]) = AAA - ZZ + 1 = 0 - (-1) + 1 = 2