python实现 1-26=A-Z, then AA-AZ, BA-BZ...ZZA-ZZZ, AAAA, etc.

Question

网上看到类似的算法，不过实现是C++.

private static void alphaseq0(int n, String alphabet, StringBuffer buf) {
        int len = alphabet.length();
        
        if (n >= len) {
               alphaseq0(n/len - 1,alphabet,buf);
               n = n % len;
        }
        
        buf.append(alphabet.charAt(n));
}

本题的题意是: 给定一个 整数 n 和 字元集 alphabet，return 一个对应的 string

而 对应的规则 如下:

(假设我们的字元集是英文字母 A-Z，也就是说这些字元是可以用来代表给定的整数的)

 1  ->    A
 2  ->    B
 3  ->    C
    ...
26  ->    Z
27  ->   AA
    ...
52  ->   AZ
    ...
 m  ->  ZZA
    ...
 n  ->  ZZZ
n+1 -> AAAA

Answer 1

這題乍看簡單，其實後來仔細研究花了我不少時間(也許是我頭腦簡單...)

本題的題意是: 給定一個 整數 和 字符集，return 一個對應的 string

而 對應的規則 如下:

(假設我們的字元集是英文字母 A-Z，也就是說這些字元是可以用來代表給定的整數的)

 1  ->    A
 2  ->    B
 3  ->    C
    ...
26  ->    Z
27  ->   AA
    ...
52  ->   AZ
    ...
 m  ->  ZZA
    ...
 n  ->  ZZZ
n+1 -> AAAA

我馬上想到了 itertools.product，我可以很簡單地去生出足夠多的 string，再從中挑選第 n 個:

from itertools import product

def get_alphaseqs(n, alphabet):
    """ get first n alphaseq """
    results = []
    for l in range(1, len(alphabet)+1):
        results.extend([''.join(p) for p in product(alphabet, repeat=l)])
        if len(results) >= n:
            return results[:n]
    return None

alphabet 的變化數量如果不夠會 return None

所以如果我想要得到 n=3000 對應的 string;

alphabet = 'abcdefghijklmnopqrstuvwxyz' 
string = get_alphaseqs(3000, alphabet)[-1]

但是這樣做的問題是: 非常耗時，理由很簡單，我產生了太多不需要的東西。對照樓主給的 C++ 範例，我應該直接產生對應的 string 就好

那該怎麼做呢? 我想起了進位轉換，這個問題不就是進位轉換的問題嗎?

比如說我們看一個 10 進位轉 16 進位的例子:

10進位            分解            16進位
---------------------------------------
  1    = 0*(16**1) +  1*(16**0) =     1
 16    = 1*(16**1) +  0*(16**0) =    10
 31    = 1*(16**1) + 15*(16**0) =    1F

以 31 為例子，我們先除一次 16 得到餘數 15，就可以查出他的第一位符號 F，接著再除第二次得到餘數 1 也可以查出他的第二位符號 1。

我們現在的對應轉換問題不就是: 要求把 10 進位 ( 10 個符號 0-9 ) 轉成 26 進位 (26 個符號 A-Z) 嗎?

那還不簡單，仿照進位轉換的作法，我只要不停連除字符集的長度 len(alphabet) (len(alphabet) 進位) 就可以查詢的到每一位的對應符號了。

可惜問題沒有那麼簡單，大家有註意到嗎? 這個對應會從1 開始而不是0，少了這個0 的對應，一切的規則似乎被打亂了許多，對於26 進位而言，十進位的26 應該是要進位了，但在這裡不是，26 對應的是單一的符號 Z ，我們必須找出規則來處理除26 餘0 的狀況。

於是我開始觀察規則:

十進位整數      1   2   ...  26   27  ...  52
對應字串        A   B   ...  Z    AA  ...  AZ
除以 26 之商    0   0   ...  1    1   ...   2
除以 26 之餘    1   2   ...  0    1   ...   0

我們會發現:

1. 如果不是整除的話(餘數不為零)，那規則跟進位轉換沒兩樣，可以直接用餘數查詢對應的符號，並且用 商 作被除數來做下一次的除法

2. 如果整除(餘數為零)，我們則必須取最後一個符號，下一次的除法要用 (商-1) 來當被除數做下一次的除法

根據這個規則我寫了兩個版本的 function，一個是如同 C++ 範例碼使用 recursive 的作法:

def int2alphaseq(n, alphbet):
    """ change int to alphaseq """
    buf = ''
    if n==0:
        return buf
    if n >= len(alphbet):
        k =  n % len(alphbet)
        if k==0:
            buf = int2alphaseq(n//len(alphbet)-1, alphbet)
        else:
            buf = int2alphaseq(n//len(alphbet), alphbet)
        n = k
    return buf + alphbet[n-1]

另一個是用 iterate 的方式:

def int2alphaseqiter(n, alphbet):
    """ change int to alphaseq """
    buf = ''
    while n >= len(alphabet):
        n, k = pmod(n, len(alphabet))
        if k==0:
            n -= 1
        buf = alphabet[k-1] + buf
    if n==0:
        return buf
    else:
        return alphabet[n-1] + buf

只要比較這三個 function 轉出來的 string 一不一樣就可以確認正確性。

如果樓主發現跟原題想要的不一樣或是大家有任何意見，歡迎在評論告訴我!

---

我回答過的問題: Python-QA