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

Soalan ini nampak mudah pada pandangan pertama, tetapi sebenarnya saya mengambil banyak masa untuk mengkajinya dengan teliti (mungkin saya berfikiran sederhana...)

Maksud soalan ini ialah: diberi integer dan set aksara, kembalikan rentetan

yang sepadan

dan peraturan yang sepadan untuk adalah seperti berikut:

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

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

Saya serta-merta memikirkan itertools.product Saya boleh menjana rentetan yang mencukupi dan memilih nyang:

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

Jika bilangan perubahan dalam

alphabet tidak mencukupi, return None

Jadi jika saya ingin mendapatkan rentetan yang sepadan dengan n=3000;

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

Tetapi masalahnya ialah: ia sangat memakan masa, atas sebab mudah saya menjana terlalu banyak barangan yang tidak perlu. Membandingkan contoh C yang diberikan oleh poster, saya harus terus menjana rentetan yang sepadan

Jadi apa yang perlu kita lakukan? Saya terfikir untuk membawa penukaran Bukankah masalah ini membawa kepada penukaran?

Sebagai contoh, mari lihat contoh menukar perpuluhan kepada perenambelasan:

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

Mengambil 31 sebagai contoh, mula-mula kita bahagikan 16 sekali untuk mendapatkan baki 15, kemudian kita boleh mengetahui simbol pertamanya F, dan kemudian bahagikannya untuk kali kedua untuk mendapatkan baki 1 dan kita juga boleh ketahui simbol keduanya Simbol bit 1.

Bukankah masalah penukaran semasa kami yang sepadan: memerlukan penukaran perpuluhan (10 simbol 0-9) kepada perenambelasan (26 simbol A-Z)?

Itu tidak mudah mengikut kaedah penukaran bawa, saya hanya perlu terus membahagikan panjang set aksara len(alphabet) (len(alphabet) bawa) untuk menanyakan simbol yang sepadan bagi setiap bit.

Malangnya, masalahnya tidak semudah itu. Adakah anda perasan? Surat-menyurat ini akan bermula dari 1 dan bukannya 0. Tanpa surat-menyurat 0, semua peraturan nampaknya banyak terganggu digit perpuluhan 26 sepatutnya dibawa, tetapi ia bukan di sini 26 sepadan dengan satu simbol Z Kita mesti mengetahui peraturan untuk mengendalikan situasi bahagi dengan 26 dan meninggalkan 0.

Jadi saya mula mematuhi peraturan:

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

Kami akan dapati:

1. Jika ia bukan integer boleh bahagi (bakinya bukan sifar), maka peraturannya adalah sama dengan penukaran bit Anda boleh terus menggunakan baki untuk menanyakan simbol yang sepadan, dan menggunakan 商 sebagai dividen untuk melakukan bahagian seterusnya

2. Jika ia adalah bahagian integer (baki sifar), kita mesti mengambil tanda terakhir, dan bahagian seterusnya mesti menggunakan (商-1) sebagai dividen untuk bahagian seterusnya

Mengikut peraturan ini, saya menulis dua versi fungsi Satu ialah menggunakan rekursif seperti kod sampel C :

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]

Cara lain ialah menggunakan 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

Selagi rentetan yang ditukar oleh ketiga-tiga fungsi ini dibandingkan, ketepatannya boleh disahkan.

Jika poster menemui sesuatu yang berbeza daripada soalan asal yang dikehendaki atau jika anda mempunyai sebarang ulasan, sila beritahu saya dalam ulasan!

---

Soalan yang saya jawab: Python-QA