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

This question seems simple at first glance, but in fact it took me a lot of time to study it carefully (maybe I am simple-minded...)

The meaning of this question is: given an integer and character set, return a corresponding string

And the corresponding rules for are as follows:

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

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

I immediately thought of 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

So if I want to get the string corresponding to n=3000;

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

But the problem with this is: it is very time-consuming, for the simple reason that I produce too much unnecessary stuff. Comparing the C++ example given by the poster, I should just generate the corresponding string directly

So what should we do? I thought of carry conversion. Isn’t this problem about carry conversion?

For example, let’s look at an example of converting decimal to hexadecimal:

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

Take 31 as an example. We first divide 16 once to get the remainder 15, and then we can find out its first symbol F，接著再除第二次得到餘數 1 也可以查出他的第二位符號 1.

Isn’t our current corresponding conversion problem: requiring the conversion of decimal (10 symbols 0-9) into 26-carry (26 symbols A-Z)?

That’s not easy. Following the method of carry conversion, I only need to keep dividing the length of the character set len(alphabet) (len(alphabet) (carry) to query the corresponding symbol of each bit.

Unfortunately, the problem is not that simple. Have you noticed? This correspondence will start from 1 instead of 0. Without the correspondence of 0, all the rules seem to be disrupted a lot. For 26-carry, the decimal 26 應該是要進位了，但在這裡不是，26 對應的是單一的符號 Z , we must find rules to handle the situation when division by 26 leaves 0.

So I started to observe the rules:

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

We will find out:

1. If it is not divisible (remainder is not zero), then the rules are the same as bit conversion. You can directly use the remainder to query the corresponding symbol, and use 商 as the dividend to do the next division

2. If the division is integer (remainder is zero), we must take the last sign, and the next division must use (商-1) as the dividend for the next division

According to this rule, I wrote two versions of function. One is using recursive like the C++ sample code:

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]

Another way is to use 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

Just compare the strings converted by these three functions to confirm the correctness.

If the poster finds something different from what the original question wanted or if you have any comments, please let me know in the comments!

---

Questions I answered: Python-QA