mip mip - 4 months ago 29
Java Question

Generating an alphabetic sequence in Java

I'm looking for a way of generating an alphabetic sequence:

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


Can anyone suggest a convenient way of doing this. What data structures can I make use of?

I'd like methods which get the next code in the sequence and then reset the sequence.

Answer

My version implements Iterator and maintains an int counter. The counter values are translated to the corresponding string:

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

Call next() on the Iterator to use it.

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

An implementation with better performance for larger sequences reuses the common prefix:

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

You'll get even better performance if you rewrite this basic algorithm with an implementation that works with arrays. (String.charAt, String.substring and StringBuffer have some overhead.)