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

この質問は一見簡単そうに見えますが、慎重に勉強するのにかなりの時間がかかりました（私の頭が単純なのかもしれません...）

この質問の意味は次のとおりです。整数と文字セットが与えられると、対応する文字列

を返します。

と、 に対応するルール は次のとおりです:

リーリー

すぐに itertools.product を思いつきました。十分な文字列を簡単に生成して、n 番目の文字列を選択できます。

リーリー

alphabet の変更数が足りない場合は、return None

n=3000に対応する文字列を取得したい場合は、

リーリー

しかし、これの問題は、不要なものが多すぎるという単純な理由で、非常に時間がかかることです。投稿者が提供する C++ の例と比較すると、対応する文字列を直接生成する必要があります

それではどうすればよいでしょうか?この問題は桁上げ変換の問題ではないでしょうか?

たとえば、10 進数を 16 進数に変換する例を見てみましょう:

リーリー

31 を例にとると、まず 16 を 1 回除算して余り 15 を取得します。次に、その最初のシンボル F を見つけます。次に、2 回目に除算して余り 1 を取得します。また、次のこともできます。 2 番目のシンボルであるビットシンボル 1 を見つけます。

現在の対応する変換問題は、10 進数 (0 ～ 9 の 10 個の記号) を 16 進数 (A ～ Z の 26 個の記号) に変換する必要があるということではありませんか?

これは簡単ではありません。キャリー変換方法に従って、文字セット len(alphabet) (len(alphabet) キャリー) の長さを分割し続けて、各ビットの対応するシンボルをクエリするだけです。

残念ながら、問題はそれほど単純ではありません。この対応は 0 ではなく 1 から始まります。0 の対応がなければ、すべてのルールが大きく崩れるようです。 10 進数 26 は桁上げされるべきですが、ここにはありません。26 は 1 つの記号 Z に対応します。26 で割って 0 を残す状況を処理する規則を見つけなければなりません。

そこで私はルールを守り始めました:

リーリー

次のものが見つかります:

1. 割り切れない整数 (剰余がゼロでない) の場合、ルールはビット変換と同じになります。剰余を直接使用して対応するシンボルをクエリし、商 を被除数として使用できます。次の除算を行うため

2. 整数の除算 (剰余がゼロ) の場合は、最後の符号を取り、次の除算では (商-1) を次の除算の被除数として使用する必要があります

このルールに従って、関数の 2 つのバージョンを作成しました。1 つは、C++ サンプル コードのように再帰を使用するものです。

リーリー

もう 1 つの方法は、反復を使用することです:

リーリー

これら3つの関数で変換された文字列を比較できれば、正しいことが確認できます。

投稿者が元の質問の意図と異なるものを見つけた場合、またはコメントがある場合は、コメントでお知らせください。

---

私が回答した質問: Python-QA