algorithm - 给定一个单词，打印其索引，单词可以相应增加

Question

想象一个单词的字母表。

例子:

 a ==> 1 
 b ==> 2 
 c ==> 3 

 z ==> 26 
 ab ==> 27 
 ac ==> 28 

 az ==> 51 
 bc ==> 52 
 and so on. 

这样字符序列只需按升序排列(ab 有效但 ba 无效)。给定任何单词，如果有效则打印其索引，否则为 0。

 Input  Output 

 ab      27 

 ba       0 

 aez     441 

在这个问题中，我可以轻松地进行数学运算，但没有得到任何算法。

我在数学中所做的是

一个字母 26

两个字母 325

.

.

.

很快

Answer 1

首先让所有的字母数字:

'aez' 将变成 1,5,26

将这些数字变量称为 ...X3,X2,X1

26 是 X1，5 是 X2，1 是 X3(注意，从右到左)

现在是神奇的公式:



即使在更糟糕的情况下，也用示例和速度演示进行编码:

def comb(n,k): #returns combinations
    p = 1 #product
    for i in range(k):
        p *= (n-i)/(i+1)
    return p

def solve(string):
    x = []
    for letter in string:
        x.append(ord(letter)-96)  #convert string to list of integers
    x = list(reversed(x))  #reverse the order of string
    #Next, the magic formula
    return x[0]+sum(comb(26,i)-comb(26-x[i-1]+1,i)*(1-i/(26-x[i-1]+1)) for i in range(2,len(x)+1))

solve('bhp')
764.0
>>> solve('afkp')
3996.0
>>> solve('abcdefghijklmnopqrstuvwxyz')
67108863.0
>>> solve('hpz')
2090.0
>>> solve('aez')
441.0
>>> if 1:
        s = ''
        for a in range(97,97+26):
                s += chr(a)
        t = time.time()
        for v in range(1000):
                temp = solve(s)
        print (time.time()-t)


0.1650087833404541

为了理解我对这个公式的解释，我需要回顾一下帕斯卡三角形和二项式定理中的一个数学事件:

这是帕斯卡三角形:



从右上角到左下角，首先是一个 1 的序列。然后是计数数字的序列。下一个序列是计数数字的总和。这些被称为三角数。下一个序列是三角形数的总和，称为四面体数，这种模式一直在继续。

现在对于二项式定理:



结合二项式定理和帕斯卡三角形，可以看出第n个三角形数为:



第 n 个四面体数为:



前 n 个四面体数之和为:



并在...

现在解释一下。对于这个解释，我将只使用 6 个字母 a-f，并将用数字 1-6 替换它们。更多字母的程序相同

如果长度为 1，则可能的序列为:

1
2
3
4
5
6

在这里，答案只是值(value)

现在长度为 2:

12  13  14  15  16
23  24  25  26
34  35  36
45  46
56

为了解决这个问题，我们将其分为 3 个部分:

求上面各行的元素总数

在这种情况下，第一行有 5 个元素，第二行有 4 个，第三行有 3 个，依此类推。我们要做的是找到一种方法来对序列 (5,4,3,2,1) 的前 n 个元素求和。为了做到这一点，我们减去三角形数。 (1+2+3+4+5)-(1+2+3) = (4+5)。类似地 (1+2+3+4+5)-(1+2) = 3+4+5。因此该值等于:

现在，我们已经考虑了目标以上的值，并且只关心它所在的列。为了找到这个，我们添加 x1-x2

最后，我们需要添加长度为 1 的序列的数量。这等于 6。因此，我们的公式是:

接下来我们将重复长度为 3 的序列:

123  124  125  126
134  135  136
145  146
156

234  235  236
245  246
256

345  346
356

456

我们再次将这个问题分成几个步骤:

查找每个数组上方有多少个元素。数组值是后向三角形数 (10, 6, 3, 1)。这一次，我们不是减去三角形数，而是减去四面体数:

注意每个单独的数组如何具有长度为 2 的序列的形状。通过从 x1 和 x2 中减去 x3，我们将序列减少到 2 次。例如，我们将从第二个数组

中减去 2

这个

234  235  236
245  246
256

变成

12  13  14
23  24
34  

我们现在可以使用长度为 2 的公式，用 6-x3 而不是 6，因为我们的序列现在有不同的最大值

最后，我们将长度为 1 和长度为 2 的序列的总数相加。事实证明，有多少特定长度的序列是有规律的。答案是组合。有 个长度为 1 的序列， 个长度为 2 的序列，依此类推。

将这些结合起来，我们长度 3 的总公式变为:



对于更长的序列，我们可以遵循这种减少模式

现在我们将正确使用我们的公式来寻找模式:

长度1:y1

长度2:



长度 3:



注意:我还使用了长度 4 来确保图案保持不变

通过一些数学运算、术语分组以及从 6 到 26 的变化，我们的公式变为:



为了进一步简化这一点，必须进行更多的数学计算。
这个等式对所有 a 和 b 都成立。对于一个快速有趣的练习，证明它(不是真的很难):



这种身份允许进一步分组和否定项以达到我们过于简化的公式: