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 个: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)

   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]

   alphabet 的变化数量如果不够会 return None

所以如果我想要得到 n=3000 对应的 string;

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

但是这样做的问题是: 非常耗时，理由很简单，我产生了太多不需要的东西。对照楼主给的 C++ 范例，我应该直接生成对应的 string 就好

那该怎么做呢? 我想起了进位转换，这个问题不就是进位转换的问题吗?

比如说我们看一个 10 进位转 16 进位的例子:

rrreee

以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 的状况。 🎜 🎜于是我开始观察规则:🎜 rrreee 🎜我们会发现:🎜

1. 🎜如果不是整除的话(余数不为零)，那规则跟进位转换没两样，可以直接用余数查询对应的符号，并且用商 作被除数来做下一次的除法🎜🎜
2. 🎜如果整除(余数为零)，我们则必须取最后一个符号，且下一次的除法要用(商-1) 来当被除数做下一次的除法🎜 🎜 🎜 🎜根据这个规则我写了两个版本的 function，一个是如同 C++ 范例码使用 recursive 的作法:🎜 rrreee 🎜另一个是用 iterate 的方式:🎜 rrreee 🎜只要比较这三个 function 转出来的 string 一不一样就可以确认正确性。 🎜 🎜如果楼主发现跟原题想要的不一样或是大家有任何意见，欢迎在评论告诉我!🎜 🎜 🎜🎜我回答过的问题🎜: Python-QA🎜