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

Cette question semble simple à première vue, mais il m'a en fait fallu beaucoup de temps pour l'étudier attentivement (je suis peut-être simple d'esprit...)

La signification de cette question est la suivante : étant donné un entier et un jeu de caractères, renvoie une chaîne correspondante

et la règle correspondante pour est la suivante :

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

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

J'ai tout de suite pensé à itertools.product Je peux facilement générer suffisamment de chaînes et sélectionner la nième :

.

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

Si le nombre de changements dans

alphabet n'est pas suffisant, return None

Donc si je veux récupérer la chaîne correspondant à n=3000;

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

Mais le problème est que cela prend beaucoup de temps, pour la simple raison que je génère trop de choses inutiles. En comparant l'exemple C donné par l'affiche, je devrais générer directement la chaîne correspondante

Alors que devons-nous faire ? J'ai pensé à la conversion de portage. Ce problème n'est-il pas un problème de conversion de portage ?

Par exemple, regardons un exemple de conversion de décimal en hexadécimal :

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

En prenant 31 comme exemple, on divise d'abord 16 une fois pour obtenir le reste 15, puis on peut trouver son premier symbole F, puis on le divise une seconde fois pour obtenir le reste 1 et on peut aussi découvrez son deuxième symbole Symbole Bit 1.

Notre problème de conversion correspondant actuel n'est-il pas : nécessiter la conversion du nombre décimal (10 symboles 0-9) en hexadécimal (26 symboles A-Z) ?

Ce n'est pas facile. Suite à la méthode de conversion carry, il me suffit de continuer à diviser la longueur du jeu de caractères len(alphabet) (len(alphabet) carry) pour interroger le symbole correspondant de chaque bit.

Malheureusement, le problème n'est pas si simple. Avez-vous remarqué ? Cette correspondance partira de 1 au lieu de 0. Sans la correspondance de 0, toutes les règles semblent être beaucoup perturbées. chiffre décimal Le 26 devrait être porteur, mais il n'est pas ici 26 correspond à un seul symbole Z Il faut connaître les règles pour gérer la situation de division par 26 et laisser 0.

J'ai donc commencé à observer les règles :

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

Nous retrouverons :

1. S'il ne s'agit pas d'un entier divisible (le reste n'est pas nul), alors les règles sont les mêmes que pour la conversion de bits. Vous pouvez directement utiliser le reste pour interroger le symbole correspondant et utiliser 商 comme dividende. faire la prochaine division

2. S'il s'agit d'une division entière (le reste est zéro), il faut prendre le dernier signe, et la division suivante doit utiliser (商-1) comme dividende pour la division suivante

Selon cette règle, j'ai écrit deux versions de fonction. L'une consiste à utiliser récursive comme l'exemple de code 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]

L'autre façon est d'utiliser itérer :

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

Tant que les chaînes converties par ces trois fonctions sont comparées, l'exactitude peut être confirmée.

Si l'affiche trouve quelque chose de différent de ce que souhaitait la question initiale ou si vous avez des commentaires, faites-le-moi savoir dans les commentaires !

---

Questions auxquelles j'ai répondu : Python-QA