算法 – 给出一个单词,打印其索引,可以相应地增加单词

想象一下字母表.

例：

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

.

.

.

所以

>首先把所有的字母数字：

”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,则可能的顺序为：

在这个答案只是价值

现在长度为2：

为了解决这个问题,我们把它分成3部分：

>查找上面行中的元素总数

>在这种情况下,第一行中有5个元素,第二行中有4个元素,第3个中的3个等等.我们要做的是找到一个方法来总结序列的前n个元素(5,4,3,2,1).为了做到这一点,我们减去三角形数字. (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：

我们再次将这个问题分解成如下步骤：

>查找每个数组以上的元素数量.阵列值是向后的三角形数字(10,6,3,1).这次,我们减去三角形数字,而不是减去四面体数字：

>

>注意每个单独的数组是否具有长度2序列的形状.通过从x1和x2中减去x3,我们将序列减少到2.例如,我们将从第二个数组中减去2

这个

变

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

>

>最后,我们添加长度1和长度2序列的总数.事实证明,有一个特定长度的序列有多少种.答案是组合.长度为1,长度为2的序列等等.

将这些我们的总配方长度为3组合成：

我们可以按照这种更长的序列的减少模式

现在我们将出发我们的公式来寻找模式：

长度1：y1

长度2：

长度3：

注意：我也使用长度4来确保模式保持

有一点数学,术语分组,从6到26的变化我们的公式变成：

为了进一步简化,必须做更多的数学.

这个身份对于所有的a和b都是正确的.为了快乐的练习,证明(不是很难)：

这个身份允许进一步分组和否定术语以达到我们过分简化的公式：