在Java中生成字母序列

Question

我正在寻找一种生成字母序列的方法：

A, B, C, ..., Z, AA, AB, AC, ..., ZZ.

有人可以建议一种方便的方法吗？我可以使用哪些数据结构？

我想要的方法是获取序列中的下一个代码，然后重置序列。

- mip

Answer 1

一个递归函数，用于将整数生成字符串的一行代码：

static String str(int i) {
    return i < 0 ? "" : str((i / 26) - 1) + (char)(65 + i % 26);
}

使用示例：

public static void main(String[] args) {
    for (int i = 0; i < 27*27; ++i) {
        System.out.println(i + " -> " + str(i));
    }
}

输出：

0 -> A
1 -> B
2 -> C
[...]
24 -> Y
25 -> Z
26 -> AA
27 -> AB
[...]
700 -> ZY
701 -> ZZ
702 -> AAA
703 -> AAB
[...]
727 -> AAZ
728 -> ABA

- jon-hanson

---

返回已翻译的文本：或从1开始返回i-- <= 0 ? "" : (char) ('A' + i % 26) + str(i / 26);。 - Eng.Fouad

如果有人需要Kotlin的等效代码，请参考以下内容：private fun str(i: Int): String { return if (i < 0) "" else str(i / 26 - 1) + (65 + i % 26).toChar() } - Levon Petrosyan

Answer 2

我将维基百科的26-进制下的双射编码法和双射进位制的性质结合起来做成了这个:

import static java.lang.Math.*;

private static String getString(int n) {
    char[] buf = new char[(int) floor(log(25 * (n + 1)) / log(26))];
    for (int i = buf.length - 1; i >= 0; i--) {
        n--;
        buf[i] = (char) ('A' + n % 26);
        n /= 26;
    }
    return new String(buf);
}

通过 Wolfram Alpha 的帮助。虽然在第一个链接中使用实现可能会更简单。

- user988346

---

维基百科的双射数码页面缺少了公式q_n=f(q_{n-1}/k)中f的定义，使其变得不具有信息性。您可以使用一行代码进行简化，即'A' + --n % 26，但这可能会牺牲清晰度。 - Adam L. S.

转念一想，我相信这是一个将数字映射到数字的函数，对吧？这将使得不管怎样都有必要阅读26进位页。 - Adam L. S.

你引用的维基百科文章（双射进位制#双射进位制的性质）中提到：如果 k > 1，则表示非负整数 n 的 k 进制数的位数是 floor(log(n+1) + log(k-1))，其中 log 是以 k 为底的对数。我花了很长时间分析这个问题，但我无法说服自己看到证明，甚至没有一个好的直觉来证明这个命题。它当然适用于我测试过的所有情况，但我想知道是否有人能够为此提供一个好的论据？我实现了两种方法，并发现递归方法要慢两倍。 - Phill Apley

这是一个证明：http://math.stackexchange.com/questions/607856/how-many-digits-are-in-the-bijective-base-k-numeral-for-n/608884#608884 - Phill Apley

顺便说一句，你的回答在这篇文章的第二点——不要用流替换循环的三个原因中得到了一些赞扬。https://blog.jooq.org/2015/12/08/3-reasons-why-you-shouldnt-replace-your-for-loops-by-stream-foreach/ - MasterJoe

Answer 3

我的版本实现了Iterator并维护一个int计数器。计数器的值被转换为相应的字符串：

import com.google.common.collect.AbstractIterator;

class Sequence extends AbstractIterator<String> {
    private int now;
    private static char[] vs;
    static {
        vs = new char['Z' - 'A' + 1];
        for(char i='A'; i<='Z';i++) vs[i - 'A'] = i;
    }

    private StringBuilder alpha(int i){
        assert i > 0;
        char r = vs[--i % vs.length];
        int n = i / vs.length;
        return n == 0 ? new StringBuilder().append(r) : alpha(n).append(r);
    }

    @Override protected String computeNext() {
        return alpha(++now).toString();
    }
}

调用Iterator上的next()方法来使用它。

Sequence sequence = new Sequence();
for(int i=0;i<100;i++){
  System.out.print(sequence.next() + " ");
}

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD AE

为了更好地处理较大序列，一种具有更优性能的实现重复利用公共前缀：

class SequencePrefix extends AbstractIterator<String> {
    private int now = -1;
    private String prefix = "";
    private static char[] vs;
    static {
        vs = new char['Z' - 'A' + 1];
        for(char i='A'; i<='Z';i++) vs[i - 'A'] = i;
    }

    private String fixPrefix(String prefix){
        if(prefix.length() == 0) return Character.toString(vs[0]);
        int last = prefix.length() - 1;
        char next = (char) (prefix.charAt(last) + 1);
        String sprefix = prefix.substring(0, last);
        return next - vs[0] == vs.length ? 
            fixPrefix(sprefix) + vs[0] : sprefix + next;
    }

    @Override protected String computeNext() {
        if(++now == vs.length) prefix = fixPrefix(prefix);
        now %= vs.length;
        return new StringBuilder().append(prefix).append(vs[now]).toString();
    }
}

如果您使用适用于数组的实现方式重写此基本算法，您将获得更好的性能。 （String.charAt，String.substring和StringBuffer具有一些开销。）

- Thomas Jung

---

一个人可以通过提示或示例来学习。不明白你是如何遵循自己的建议的。 - Thomas Jung

我最终使用的方法并不像这个那么聪明。我只是在对象实例化时用所有可能的代码填充了一个ArrayList，然后通过迭代器访问下一个代码。这对我的要求已经足够了。 - mip

但是你的解决方案非常完美。如果你不需要更多功能，也找不到通用实现，那么简单的实现就是正确的选择。你的实现可以有更好的性能 - 所有值都被缓存了。 - Thomas Jung

不错！我已经将你的解决方案移植到C#了；谢谢 :) - rynkadink

Answer 4

public class SeqGen {
    public static void main(String[] args) {
        //This is the configurable param
        int seqWidth = 3;

        Double charSetSize = 26d;

        // The size of the array will be 26 ^ seqWidth. ie: if 2 chars wide, 26
        // * 26. 3 chars, 26 * 26 * 26
        Double total = Math.pow(charSetSize, (new Integer(seqWidth)).doubleValue());

        StringBuilder[] sbArr = new StringBuilder[total.intValue()];
        // Initializing the Array
        for(int j = 0; j <total; j++){
            sbArr[j] = new StringBuilder();
        }

        char ch = 'A';
        // Iterating over the entire length for the 'char width' number of times.
        // TODO: Can these iterations be reduced?
        for(int k = seqWidth; k >0; k--){
            // Iterating and adding each char to the entire array.        
            for(int l = 1; l <=total; l++){
                sbArr[l-1].append(ch);
                if((l % (Math.pow(charSetSize, k-1d))) == 0){
                    ch++;
                    if(ch > 'Z'){
                        ch = 'A';
                    }
                }
            }
        }

        //Use the stringbuilder array.
        for (StringBuilder builder : sbArr) {
            System.out.println(builder.toString());
        }
    }
}

请参考示例，根据您的需求进行修改。

- Hemant Metalia

Answer 5

我已经创建了以下的迭代和递归解决方案。在这些解决方案之后，您将找到一个示例，展示如何使用迭代器生成n个项目的序列。此外，我还为了好玩而对我的递归解决方案进行了代码高尔夫。

解决方案

迭代

public static String indexToColumnItr(int index, char[] alphabet) {
    if (index <= 0)
        throw new IndexOutOfBoundsException("index must be a positive number");
    if (index <= alphabet.length)
        return Character.toString(alphabet[index - 1]);
    StringBuffer sb = new StringBuffer();
    while (index > 0) {
        sb.insert(0, alphabet[--index % alphabet.length]);
        index /= alphabet.length;
    }
    return sb.toString();
}

递归

public static String indexToColumnRec(int index, char[] alphabet) {
    if (index <= 0)
        throw new IndexOutOfBoundsException("index must be a positive number");
    if (index <= alphabet.length)
        return Character.toString(alphabet[index - 1]);
    return indexToColumnRec(--index / alphabet.length, alphabet) + alphabet[index % alphabet.length];
}

使用方法

public static final char[] ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();

indexToColumnItr(703, ALPHABET); // AAA

---

例子

下面的代码生成了一个大小为52的序列：

[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, AA, AB, AC, AD, AE, AF, AG, AH, AI, AJ, AK, AL, AM, AN, AO, AP, AQ, AR, AS, AT, AU, AV, AW, AX, AY, AZ]

Main.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(AlphaUtils.generateSequence(52)));
    }
}

AlphaIterator.java

import java.util.Iterator;

public class AlphaIterator implements Iterator<String> {
    private int maxIndex;
    private int index;
    private char[] alphabet;

    public AlphaIterator() {
        this(Integer.MAX_VALUE);
    }

    public AlphaIterator(int maxIndex) {
        this(maxIndex, "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray());
    }

    public AlphaIterator(char[] alphabet) {
        this(Integer.MAX_VALUE, alphabet);
    }

    public AlphaIterator(int maxIndex, char[] alphabet) {
        this.maxIndex = maxIndex;
        this.alphabet = alphabet;
        this.index = 1;
    }

    @Override
    public boolean hasNext() {
        return this.index < this.maxIndex;
    }

    @Override
    public String next() {
        return AlphaUtils.indexToColumnItr(this.index++, this.alphabet);
    }
}

AlphaUtils.java

public class AlphaUtils {
    // Iterative
    public static String indexToColumnItr(int index, char[] alphabet) {
        if (index <= 0) throw new IndexOutOfBoundsException("index must be a positive number");
        if (index <= alphabet.length) return Character.toString(alphabet[index - 1]);
        StringBuffer sb = new StringBuffer();
        while (index > 0) {
            sb.insert(0, alphabet[--index % alphabet.length]);
            index /= alphabet.length;
        }
        return sb.toString();
    }

    // Recursive
    public static String indexToColumnRec(int index, char[] alphabet) {
        if (index <= 0) throw new IndexOutOfBoundsException("index must be a positive number");
        if (index <= alphabet.length) return Character.toString(alphabet[index - 1]);
        return indexToColumnRec(--index / alphabet.length, alphabet) + alphabet[index % alphabet.length];
    }

    public static String[] generateSequence(int size) {
        String[] sequence = new String[size];
        int i = 0;
        for (AlphaIterator it = new AlphaIterator(size); it.hasNext();) {
            sequence[i++] = it.next();
        }
        return sequence;
    }
}

代码高尔夫（89字节）:-)

String f(int i,char[]a){int l=a.length;return i<=0?"?":i<=l?""+a[i-1]:f(--i/l,a)+a[i%l];}

- Mr. Polywhirl

Answer 6

该方法生成字母序列。

如果传入 null，则返回 A。如果传入 A，则返回 B。

该序列依次为 A、B、C......Z、AA、AB、AC......AZ、BA、BB、BC......BZ、CA、CB、CC......CZ、DA......ZA、ZB......ZZ、AAA、AAB、AAC......AAZ、ABA、ABB......AZZ、BAA、BAB......ZZZ。

/**
* @param charSeqStr
* @return
*/

public static String getNextAlphaCharSequence(String charSeqStr) {

    String nextCharSeqStr       = null;
    char[] charSeqArr           = null;
    boolean isResetAllChar      = false;
    boolean isResetAfterIndex   = false;
    Integer resetAfterIndex     = 0;

    if (StringUtils.isBlank(charSeqStr)) {
        charSeqArr = new char[] { 'A' };
    } else {
        charSeqArr = charSeqStr.toCharArray();
        Integer charSeqLen = charSeqArr.length;

        for (int index = charSeqLen - 1; index >= 0; index--) {
            char charAtIndex = charSeqArr[index];

            if (Character.getNumericValue(charAtIndex) % 35 == 0) {
                if (index == 0) {
                    charSeqArr = Arrays.copyOf(charSeqArr, charSeqLen + 1);
                    isResetAllChar = true;
                } else {
                    continue;
                }
            } else {
                char nextCharAtIndex = (char) (charAtIndex + 1);
                charSeqArr[index] = nextCharAtIndex;
                if (index + 1 < charSeqLen) {
                    isResetAfterIndex = true;
                    resetAfterIndex = index;
                }
                break;
            }
        }
        charSeqLen = charSeqArr.length;
        if (isResetAllChar) {
            for (int index = 0; index < charSeqLen; index++) {
                charSeqArr[index] = 'A';
            }
        } else if (isResetAfterIndex) {
            for (int index = resetAfterIndex + 1; index < charSeqLen; index++) {
                charSeqArr[index] = 'A';
            }
        }
    }

    nextCharSeqStr = String.valueOf(charSeqArr);
    return nextCharSeqStr;
}

public static void main(String args[]) {
    String nextAlphaSequence = null;
    for (int index = 0; index < 1000; index++) {
        nextAlphaSequence = getNextAlphaCharSequence(nextAlphaSequence);
        System.out.print(nextAlphaSequence + ",");
    }
}

- Murali

Answer 7

有趣的是，目前还没有人提供基于Java 8的函数式解决方案。以下是使用jOOλ提供的功能的解决方案，例如用于字符的range()，foldLeft()和crossJoin()（免责声明，我在维护jOOλ的公司工作）：

int max = 3;

List<String> alphabet = Seq
    .rangeClosed('A', 'Z')
    .map(Object::toString)
    .toList();

Seq.rangeClosed(1, max)
   .flatMap(length ->
       Seq.rangeClosed(1, length - 1)
          .foldLeft(Seq.seq(alphabet), (s, i) -> s.crossJoin(Seq.seq(alphabet))
                                                  .map(t -> t.v1 + t.v2)))
   .forEach(System.out::println);

这个解决方案并不是很快（例如这个）。我只是为了完整性而添加它。

- Lukas Eder

Answer 8

我建议使用迭代器返回下一个值。

迭代器需要能够创建要返回的字符串，基于内部计数器。对于您的示例，只需要两个计数器。一个用于字符串中的第一个字符，另一个用于第二个字符。

每个计数器可以对应于"ABCDEFGHIJKLMNOPQRSTUVWXYZ"中的索引。当您返回一个字符串时，更新最后一个位置的计数器。如果它超出范围，请将其重置为指向“A”并增加下一个计数器。当该计数器变得过大时，无论您需要什么，都可以让迭代器表示没有更多的元素，或将其重置为指向“ ”。

请注意，通过在第一个位置上放置一个空格，您可以使用trim()函数去除任何空格，从而使第一个响应变为“A”。

- Thorbjørn Ravn Andersen

Answer 9

将'A'到'Z'看做26进制。

示例（C++）

    vector<string> generateSequenceBySize(int N)
    {
        if(N<1)
            return vector<string>();
        int base = 26;
        vector<string> seqs;
        for(int i=0;i<pow(base,N);i++)
        {
            int value = i;
            string tmp(N,'A');
            for (int j=0;j<N;j++)
            {
                tmp[N-1-j] = 'A'+value%base;
                value = value/base;
            }
            seqs.push_back(tmp);
        }
        return seqs;
    }
    vector<string> generateSequence()
    {
        //https://dev59.com/-Woy5IYBdhLWcg3wMLOj
        //A, B, C, ..., Z, AA, AB, AC, ..., ZZ.
        vector<string> seqs;
        for (int i=1;i<=2;i++)
        {
            vector<string> subSeq = generateSequenceBySize(i);
            seqs.insert(seqs.end(),subSeq.begin(),subSeq.end());
        }
        return seqs;
    }

- user5461120

Answer 10

    char ch;
    String str1 = "";
    String str2 = "";

    for (ch = 'A'; ch <= 'Z'; ch++) {
        str1 += ch;
        for (int i = 0; i < 26; i++) {
            char upper = (char) ('A' + i);
            str2 = str2 + ch + upper + " ";

        }
    }

    System.out.println(str1 + ", " + str2);

- GIRI