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

1. 首先使所有字母数字：
   • 'aez' 将变为 1,5,26
2. 将这些数字变量称为 ...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 个字母 af，并将它们替换为数字 1-6。程序相同，字母更多

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

1
2
3
4
5
6

在这个答案就是价值

现在长度为 2：

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

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

1. 查找上面行中的元素总数
   • 在这种情况下，第一行有 5 个元素，第二行有 4 个，第三行有 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。因此该值等于：
     • 
2. 现在，我们已经考虑了高于目标的值，并且只关心它所在的列。要找到它，我们添加 x1-x2
3. 最后，我们需要添加长度为 1 的序列的数量。这等于 6。因此，我们的公式是：
   • 

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

123  124  125  126
134  135  136
145  146
156

234  235  236
245  246
256

345  346
356

456

我们再一次把这个问题分成几个步骤：

1. 找出每个数组上方有多少元素。数组值是倒三角数 (10, 6, 3, 1)。这一次，我们减去四面体数，而不是减去三角形数：
   • 
2. 请注意每个单独的数组如何具有长度为 2 的序列的形状。通过从 x1 和 x2 中减去 x3，我们将序列减少到 2 次。例如，我们将从第二个数组中减去 2

这个

234  235  236
245  246
256

变成

12  13  14
23  24
34  

3. 我们现在可以使用长度为 2 的公式，用 6-x3 代替 6，因为我们的序列现在有不同的最大值
   • 
4. 最后，我们添加长度为 1 和长度为 2 的序列的总数。事实证明，有多少特定长度的序列是有规律的。答案是组合。有长度为 1 的序列，长度为 2 的序列，依此类推。

结合这些，我们的长度为 3 的总公式变为：

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

现在我们将纠正我们的公式来寻找模式：

长度1：y1

长度 2：

长度 3：

注意：我还使用了长度 4 来确保模式保持不变

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

为了进一步简化这一点，必须做更多的数学运算。
这个恒等式适用于所有 a 和 b。对于一个快速有趣的练习，证明它（不是很困难）：

这个恒等式允许进一步对术语进行分组和否定，以达到我们过于简化的公式：

Answer 2

这是两个问题的组合：解析基数不是 10 的数字并确定输入是否已排序。

请注意，由于这可能是家庭作业，因此您可能不能只使用现有方法来完成艰苦的工作。

Answer 3

对于这个假想字母表中长度超过一个字符的字母，我们可以使用递归：

XnXn-1..X1 = 
  max(n-1) 
      + (max(n-1) - last (n-1)-character letter before 
                    the first (n-1)-character letter after a)
  ... + (max(n-1) - last (n-1)-character letter before the
                    first (n-1)-character letter after the-letter-before-Xn)
  + 1 + ((Xn-1..X1) - first (n-1)-character letter after Xn)

where max(1) = z, max(2) = yz...

哈斯克尔代码：

import Data.List (sort)
import qualified Data.MemoCombinators as M

firstAfter letter numChars = take numChars $ tail [letter..]

lastBefore letter numChars = [toEnum (fromEnum letter - 1) :: Char] 
                          ++ reverse (take (numChars - 1) ['z','y'..])

max' numChars = reverse (take numChars ['z','y'..])

loop letter numChars = 
  foldr (\a b -> b 
                 + index (max' numChars) 
                 - index (lastBefore (head $ firstAfter a numChars) numChars)
        ) 0 ['a'..letter]

index = M.list M.char index' where
  index' letter
    | null (drop 1 letter)  = fromEnum (head letter) - 96
    | letter /= sort letter = 0
    | otherwise = index (max' (len - 1))
                + loop (head $ lastBefore xn 1) (len - 1)
                + 1
                + index (tail letter) - index (firstAfter xn (len - 1))
   where len = length letter
         xn = head letter

输出：

*Main> index "abcde"
17902

*Main> index "abcdefghijklmnopqrstuvwxyz"
67108863
(0.39 secs, 77666880 bytes)

Answer 4

Base 26 编号系统。我建议您查看八进制、十进制和十六进制编号系统，一旦您了解如何将它们中的任何一个转换为十进制，您也会知道这一点。

Answer 5

我写了一个蛮力程序，根据原始海报提供的标准计算一、二、三、四和五个字母单词的数量。

想象一个单词的字母表，一个单词中的字符序列只能按升序排列。

这是我的程序的结果：

One letter words   - 26
Two letter words   - 325
Three letter words - 2600
Four letter words  - 14950
Five letter words  - 65780

Total words        - 83681

我的“解决方案”是生成一个包含从 a 到 abcdefghijklmnopqrstuvwxyz 的所有单词的字典。

这是我使用的代码：

public class WordSequence implements Runnable {
    
    private int wordCount = 0;

    @Override
    public void run() {
        int count = createOneLetterWords();
        System.out.println("One letter words   - " + count);
        count = createTwoLetterWords();
        System.out.println("Two letter words   - " + count);
        count = createThreeLetterWords();
        System.out.println("Three letter words - " + count);
        count = createFourLetterWords();
        System.out.println("Four letter words  - " + count);
        count = createFiveLetterWords();
        System.out.println("Five letter words  - " + count);
        
        System.out.println("\nTotal words        - " + wordCount);
    }
    
    private int createOneLetterWords() {
        int count = 0;
        
        for (int i = 0; i < 26; i++) {
            createWord(i);
            wordCount++;
            count++;
        }
        return count;
    }
    
    private int createTwoLetterWords() {
        int count = 0;
        
        for (int i = 0; i < 25; i++) {
            for (int j = i + 1; j < 26; j++) {
                createWord(i, j);
                wordCount++;
                count++;
            }
        }
        return count;
    }
    
    private int createThreeLetterWords() {
        int count = 0;
        
        for (int i = 0; i < 24; i++) {
            for (int j = i + 1; j < 25; j++) {
                for (int k = j + 1; k < 26; k++) {
                    createWord(i, j, k);
                    wordCount++;
                    count++;
                }
            }
        }
        return count;
    }
    
    private int createFourLetterWords() {
        int count = 0;
        
        for (int i = 0; i < 23; i++) {
            for (int j = i + 1; j < 24; j++) {
                for (int k = j + 1; k < 25; k++) {
                    for (int m = k + 1; m < 26; m++) {
                        createWord(i, j, k, m);
                        wordCount++;
                        count++;
                    }
                }
            }
        }
        return count;
    }
    
    private int createFiveLetterWords() {
        int count = 0;
        
        for (int i = 0; i < 22; i++) {
            for (int j = i + 1; j < 23; j++) {
                for (int k = j + 1; k < 24; k++) {
                    for (int m = k + 1; m < 25; m++) {
                        for (int n = m + 1; n < 26; n++) {
                            createWord(i, j, k, m, n);
                            wordCount++;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
    
    private String createWord(int... letter) {
        StringBuilder builder = new StringBuilder();
        
        for (int i = 0; i < letter.length; i++) {
            builder.append((char) (letter[i] + 'a'));
        }
        
        return builder.toString();
    }
    
    public static void main(String[] args) {
        new WordSequence().run();
    }

}