在Java中生成字母序列

Question

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

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

任何人都可以建议一种方便的方法.我可以使用哪些数据结构？

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

Answer 1

我结合维基百科的Hexavigesimal#Bijective base-26和Bijective numeration#属性的双射基数k来实现:

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的帮助下.也许在第一个链接中使用实现会更简单.

Answer 2

用于从整数生成字符串的单行递归函数:

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

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() + " ");
}

ABCDEFGHIJKLMNOPQRSTU VWXYZ 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有一些开销.)