Я ищу способ генерации алфавитной последовательности:
A, B, C, ..., Z, AA, AB, AC, ..., ZZ.
Может ли кто-нибудь предложить удобный способ сделать это. Какие структуры данных я могу использовать?
Мне нужны методы, которые получают следующий код в последовательности, а затем reset последовательность.
Моя версия реализует 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();
}
}
Вызовите next() в Iterator, чтобы использовать его.
Sequence sequence = new Sequence();
for(int i=0;i<100;i++){
System.out.print(sequence.next() + " ");
}
A B C D E F G H я 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 имеют некоторые накладные расходы.)
Я объединил Википедию Hexavigesimal # Bijective base-26 и Bijective numeration # Свойства биективных цифр base-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. Возможно, было бы проще просто использовать реализацию в первой ссылке.
Однострочная рекурсивная функция для генерации строки из целого числа:
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
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());
}
}
}
обратитесь к пример и измените в соответствии с вашими требованиями.
Я создал итеративное и рекурсивное решение ниже. Вы найдете пример, следующий за этими решениями, который показывает, как генерировать 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]
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
System.out.println(Arrays.toString(AlphaUtils.generateSequence(52)));
}
}
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);
}
}
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;
}
}
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];}
Я тестировал, но код плохой...
Я сделал свой код, что работает до 256, но вы можете изменить его в соответствии с потребностями.
public static String IntToLetter(int Int) {
if (Int<27){
return Character.toString((char)(Int+96));
} else {
if (Int%26==0) {
return IntToLetter((Int/26)-1)+IntToLetter((Int%26)+1);
} else {
return IntToLetter(Int/26)+IntToLetter(Int%26);
}
}
}
EDITED (метод исправлен):
public static String IntToLetter(int Int) {
if (Int<27){
return Character.toString((char)(Int+96));
} else {
if (Int%26==0) {
return IntToLetter((Int/26)-1)+IntToLetter(((Int-1)%26+1));
} else {
return IntToLetter(Int/26)+IntToLetter(Int%26);
}
}
}
Тестирование моего кода:
for (int i = 1;i<256;i++) {
System.out.println("i="+i+" -> "+IntToLetter(i));
}
Результат
i=1 -> a
i=2 -> b
i=3 -> c
i=4 -> d
i=5 -> e
i=6 -> f
i=7 -> g
i=8 -> h
i=9 -> i
i=10 -> j
i=11 -> k
i=12 -> l
i=13 -> m
i=14 -> n
i=15 -> o
i=16 -> p
i=17 -> q
i=18 -> r
i=19 -> s
i=20 -> t
i=21 -> u
i=22 -> v
i=23 -> w
i=24 -> x
i=25 -> y
i=26 -> z
i=27 -> aa
i=28 -> ab
i=29 -> ac
i=30 -> ad
i=31 -> ae
i=32 -> af
i=33 -> ag
i=34 -> ah
i=35 -> ai
i=36 -> aj
i=37 -> ak
i=38 -> al
i=39 -> am
i=40 -> an
i=41 -> ao
i=42 -> ap
i=43 -> aq
i=44 -> ar
i=45 -> as
i=46 -> at
i=47 -> au
i=48 -> av
i=49 -> aw
i=50 -> ax
i=51 -> ay
i=52 -> az
i=53 -> ba
i=54 -> bb
i=55 -> bc
i=56 -> bd
i=57 -> be
i=58 -> bf
i=59 -> bg
i=60 -> bh
i=61 -> bi
i=62 -> bj
i=63 -> bk
i=64 -> bl
i=65 -> bm
i=66 -> bn
i=67 -> bo
i=68 -> bp
i=69 -> bq
i=70 -> br
i=71 -> bs
i=72 -> bt
i=73 -> bu
i=74 -> bv
i=75 -> bw
i=76 -> bx
i=77 -> by
i=78 -> bz
i=79 -> ca
i=80 -> cb
i=81 -> cc
i=82 -> cd
i=83 -> ce
i=84 -> cf
i=85 -> cg
i=86 -> ch
i=87 -> ci
i=88 -> cj
i=89 -> ck
i=90 -> cl
i=91 -> cm
i=92 -> cn
i=93 -> co
i=94 -> cp
i=95 -> cq
i=96 -> cr
i=97 -> cs
i=98 -> ct
i=99 -> cu
i=100 -> cv
i=101 -> cw
i=102 -> cx
i=103 -> cy
i=104 -> cz
i=105 -> da
i=106 -> db
i=107 -> dc
i=108 -> dd
i=109 -> de
i=110 -> df
i=111 -> dg
i=112 -> dh
i=113 -> di
i=114 -> dj
i=115 -> dk
i=116 -> dl
i=117 -> dm
i=118 -> dn
i=119 -> do
i=120 -> dp
i=121 -> dq
i=122 -> dr
i=123 -> ds
i=124 -> dt
i=125 -> du
i=126 -> dv
i=127 -> dw
i=128 -> dx
i=129 -> dy
i=130 -> dz
i=131 -> ea
i=132 -> eb
i=133 -> ec
i=134 -> ed
i=135 -> ee
i=136 -> ef
i=137 -> eg
i=138 -> eh
i=139 -> ei
i=140 -> ej
i=141 -> ek
i=142 -> el
i=143 -> em
i=144 -> en
i=145 -> eo
i=146 -> ep
i=147 -> eq
i=148 -> er
i=149 -> es
i=150 -> et
i=151 -> eu
i=152 -> ev
i=153 -> ew
i=154 -> ex
i=155 -> ey
i=156 -> ez
i=157 -> fa
i=158 -> fb
i=159 -> fc
i=160 -> fd
i=161 -> fe
i=162 -> ff
i=163 -> fg
i=164 -> fh
i=165 -> fi
i=166 -> fj
i=167 -> fk
i=168 -> fl
i=169 -> fm
i=170 -> fn
i=171 -> fo
i=172 -> fp
i=173 -> fq
i=174 -> fr
i=175 -> fs
i=176 -> ft
i=177 -> fu
i=178 -> fv
i=179 -> fw
i=180 -> fx
i=181 -> fy
i=182 -> fz
i=183 -> ga
i=184 -> gb
i=185 -> gc
i=186 -> gd
i=187 -> ge
i=188 -> gf
i=189 -> gg
i=190 -> gh
i=191 -> gi
i=192 -> gj
i=193 -> gk
i=194 -> gl
i=195 -> gm
i=196 -> gn
i=197 -> go
i=198 -> gp
i=199 -> gq
i=200 -> gr
i=201 -> gs
i=202 -> gt
i=203 -> gu
i=204 -> gv
i=205 -> gw
i=206 -> gx
i=207 -> gy
i=208 -> gz
i=209 -> ha
i=210 -> hb
i=211 -> hc
i=212 -> hd
i=213 -> he
i=214 -> hf
i=215 -> hg
i=216 -> hh
i=217 -> hi
i=218 -> hj
i=219 -> hk
i=220 -> hl
i=221 -> hm
i=222 -> hn
i=223 -> ho
i=224 -> hp
i=225 -> hq
i=226 -> hr
i=227 -> hs
i=228 -> ht
i=229 -> hu
i=230 -> hv
i=231 -> hw
i=232 -> hx
i=233 -> hy
i=234 -> hz
i=235 -> ia
i=236 -> ib
i=237 -> ic
i=238 -> id
i=239 -> ie
i=240 -> if
i=241 -> ig
i=242 -> ih
i=243 -> ii
i=244 -> ij
i=245 -> ik
i=246 -> il
i=247 -> im
i=248 -> in
i=249 -> io
i=250 -> ip
i=251 -> iq
i=252 -> ir
i=253 -> is
i=254 -> it
i=255 -> iu
С наилучшими пожеланиями
Этот метод генерирует последовательность альфа-символов
Если вызывается с нулевым значением, он возвращает 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 + ",");
}
}
Я бы предложил, чтобы итератор возвращал следующее значение.
Итератор должен иметь возможность создавать возвращаемую строку на основе внутренних счетчиков. Для вашего примера этого было бы достаточно с двумя счетчиками. Один для первого символа в строке, а второй для второго символа.
Каждый счетчик может соответствовать индексу в " ABCDEFGHIJKLMNOPQRSTUVWXYZ". Когда вы вернете строковое обновление счетчика для последней позиции. Если он падает "по краю" reset, он указывает на "A" и увеличивает следующий счетчик. Когда этот счетчик достигнет большого значения, пусть итератор указывает, что больше элементов нет или reset он указывает на "" в зависимости от того, что вам нужно.
Обратите внимание, что, имея первую позицию пустым, вы можете использовать trim() в строке, чтобы избавиться от любых пробелов, дающих "A" для первого ответа.
Интересно, что никто пока не предоставил функциональное решение на базе 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);
Это решение не очень быстро (например, как этот). Я только что добавил его для полноты.
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);
Это создаст последовательность для переданного значения.
/**
* Method that returns batch names based on passed value
* @param batchCount
* @return String[]
*/
public static String[] getBatchNamesForExecutor(int batchCount) {
// Batch names array
String[] batchNames = new String[batchCount];
// Loop from 0 to batchCount required
for(int index=0; index < batchCount; index++) {
// Alphabet for current batch name
int alphabet = index%26;
// iteration count happened on all alphabets till now
int iterations = index/26;
// initializing array element to blank string
batchNames[index] = "";
// Looping over the iterationIndex and creating batch alphabet prefix / prefixes
for(int iterationIndex = 0; iterationIndex < iterations; iterationIndex+=26){
batchNames[index] += String.valueOf((char)('A' + (iterations-1) % 26 ));
}
// Adding last alphabet in batch name
batchNames[index] += String.valueOf((char)('A' + alphabet % 26 ));
}
return batchNames;
}
public static void main(String[] args) {
for(String s: getBatchNamesForExecutor(8)) {
System.err.println(s);
}
System.exit(0);
}
Просто потому, что мне нравится короткий код... вдохновленный Томас Юнгс отвечает:
static String asLetters(long value) {
int codePoint = (int) ('A' + --value % 26);
long higher = value / 26;
String letter = new String(Character.toChars(codePoint));
return higher == 0 ? letter : asLetters(higher).concat(letter);
}
Начинается с 1 → a до Long.MAX_VALUE → CRPXNLSKVLJFHG. Используйте 'a' вместо 'a' для строчных букв.
возьмите 'A'to'Z' как 26radix. Пример (С++)
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()
{
//http://stackoverflow.com/questions/8710719/generating-an-alphabetic-sequence-in-java
//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;
}
Я не знаком с функциональным программированием на Java, но я предполагаю, что вы могли бы сделать что-то эквивалентное этому коду в Haskell:
- создать список ["A".. "Z"]
uca = map (: []) ['A'.. 'Z']
- декартово произведение двух списков строк, ++ объединяет две строки
cp lst1 lst2 =
[x ++ y | x <- lst1, y <- lst2]- следующее дает необходимый список строк
uca ++ cp uca uca
Все эти длинные ответы... и те, которые используют рекурсию... вау. Это может быть сделано в Java в несколько строк без рекурсии:
private static String intToValueKey(int value) {
final StringBuilder sb = new StringBuilder(String.valueOf((char)('A'+(value % 26))));
while((value = (value/26-1)) >= 0) {
sb.append((char)('A'+(value % 26)));
}
return sb.reverse().toString();
}
Затем вы просто вызываете метод с увеличением числового значения в цикле, чтобы сгенерировать последовательность от 0 до n.
for(int i=0; i<800; i++) {
System.out.println(intToValueKey(i));
}
Обратный() в конце, просто, если вы заботитесь о порядке букв и не нужен, если вы просто ищете уникальную перестановку.
// Java program to find Excel
// column name from a given
// column number
public class ExcelColumnTitle
{
// Function to print Excel column
// name for a given column number
private static void printString(int columnNumber)
{
// To store result (Excel column name)
StringBuilder columnName = new StringBuilder();
while (columnNumber > 0)
{
// Find remainder
int rem = columnNumber % 26;
// If remainder is 0, then a
// 'Z' must be there in output
if (rem == 0)
{
columnName.append("Z");
columnNumber = (columnNumber / 26) - 1;
}
else // If remainder is non-zero
{
columnName.append((char)((rem - 1) + 'A'));
columnNumber = columnNumber / 26;
}
}
// Reverse the string and print result
System.out.println(columnName.reverse());
}
// Driver program to test above function
public static void main(String[] args)
{
printString(26);
printString(51);
printString(52);
printString(80);
printString(676);
printString(702);
printString(705);
}
}
//Этот код предоставлен Харикришнаном Раджаном
Источник: https://www.geeksforgeeks.org/find-excel-column-name-given-number/
Почему рекурсивно не создавать последовательность?
Пример (непроверенный):
public String createSequenceElement(int index) {
String sequenceElement = "";
int first = index / 26;
int second = index % 26;
if (first < 1) {
sequenceElement += (char) ('A' + second);
} else {
sequenceElement += createSequenceElement(first) + (char) ('A' + second);
}
return sequenceElement ;
}
public static void main(String[] args) {
String sequence = "";
for (int i = 0; i < 100; i++) {
if (i > 0) {
sequence += ", ";
}
sequence += createSequenceElement(i);
}
System.out.println(sequence);
}