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을 한 번 나누어 나머지 15를 얻은 다음 첫 번째 기호 F를 찾은 다음 두 번째로 나누어 나머지 1를 얻습니다. 두 번째 기호 비트 기호 1를 알아보세요.

현재 해당 변환 문제는 10진수(10개의 기호 0-9)를 16진수(26개의 기호 A-Z)로 변환해야 하는 문제 아닌가요?

캐리 변환 방법에 따르면, 각 비트의 해당 기호를 쿼리하려면 문자 집합 len(alphabet)(len(alphabet) 캐리)의 길이를 계속 나누어야 합니다.

안타깝게도 문제는 그렇게 간단하지 않습니다. 이 대응은 0이 아닌 1부터 시작됩니다. 0의 대응이 없으면 모든 규칙이 많이 혼란스러워 보입니다. 십진수 26가 있어야 하는데 여기에는 없습니다. 26는 단일 기호 Z에 해당합니다. 26으로 나누고 0을 남겨두는 상황을 처리하는 규칙을 찾아야 합니다.

그래서 저는 규칙을 준수하기 시작했습니다.

으아악

우리는 다음을 찾을 것입니다:

1. 나누기가 가능한 정수가 아닌 경우(나머지가 0이 아닌 경우) 규칙은 비트 변환과 동일합니다. 나머지를 직접 사용하여 해당 기호를 쿼리하고 피제수로 商을 사용할 수 있습니다. 다음 분할을 하려고

2. 정수 나누기(나머지는 0)인 경우 마지막 부호를 가져와야 하며 다음 나누기는 (商-1)을 다음 나누기의 피제수로 사용해야 합니다.

이 규칙에 따라 두 가지 버전의 함수를 작성했습니다. 하나는 C++ 샘플 코드와 같은 재귀를 사용하는 것입니다.

으아악

다른 방법은 반복을 사용하는 것입니다.

으아악

이 세 가지 함수로 변환된 문자열을 비교하면 정확성을 확인할 수 있습니다.

포스터 내용이 원래 질문이 원했던 내용과 다른 점이 있거나, 의견이 있으시면 댓글로 알려주세요!

---

내가 답변한 질문: Python-QA