How to increment a java String through all the possibilities?

Question

I need to increment a String in java from "aaaaaaaa" to "aaaaaab" to "aaaaaac" up through the alphabet, then eventually to "aaaaaaba" to "aaaaaabb" etc. etc.

Is there a trick for this?

Answer 1

I would create a character array and increment the characters individually. Strings are immutable in Java, so each change would create a new spot on the heap resulting in memory growing and growing.

With a character array, you shouldn't have that problem...

Answer 2

Have an array of byte that contain ascii values, and have loop that increments the far right digit while doing carry overs.

Then create the string using

public String(byte[] bytes, String charsetName)

Make sure you pass in the charset as US-ASCII or UTF-8 to be unambiguous.

Answer 3

You're basically implementing a Base 26 number system with leading "zeroes" ("a").

You do it the same way you convert a int to a base-2 or base-10 String, but instead of using 2 or 10, you use 26 and instead of '0' as your base, you use 'a'.

In Java you can easily use this:

public static String base26(int num) {
  if (num < 0) {
    throw new IllegalArgumentException("Only positive numbers are supported");
  }
  StringBuilder s = new StringBuilder("aaaaaaaa");
  for (int pos = 7; pos >= 0 && num > 0 ; pos--) {
    char digit = (char) ('a' + num % 26);
    s.setCharAt(pos, digit);
    num = num / 26;
  }
  return s.toString();
}

The basic idea then is to not store the String, but just some counter (int an int or a long, depending on your requirements) and to convert it to the String as needed. This way you can easily increase/decrease/modify your counter without having to parse and re-create the String.

Answer 4

Increment the last character, and if it reaches Z, reset it to A and move to the previous characters. Repeat until you find a character that's not Z. Because Strings are immutable, I suggest using an array of characters instead to avoid allocating lots and lots of new objects.

public static void incrementString(char[] str)
{
    for(int pos = str.length - 1; pos >= 0; pos--)
    {
        if(Character.toUpperCase(str[pos]) != 'Z')
        {
            str[pos]++;
            break;
        }
        else
            str[pos] = 'z';
    }
}

Answer 5

It's not much of a "trick", but this works for 4-char strings. Obviously it gets uglier for longer strings, but the idea is the same.

char array[] = new char[4];
for (char c0 = 'a'; c0 <= 'z'; c0++) {
  array[0] = c0;
  for (char c1 = 'a'; c1 <= 'z'; c1++) {
    array[1] = c1;
    for (char c2 = 'a'; c2 <= 'z'; c2++) {
      array[2] = c2;
      for (char c3 = 'a'; c3 <= 'z'; c3++) {
        array[3] = c3;
        String s = new String(array);
        System.out.println(s);
      }
    }
  }
}

Answer 6

Just expanding on the examples, as to Implementation, consider putting this into a Class... Each time you call toString of the Class it would return the next value:

public class Permutator {

    private int permutation;

    private int permutations; 

    private StringBuilder stringbuilder;

    public Permutator(final int LETTERS) {

        if (LETTERS < 1) {
            throw new IllegalArgumentException("Usage: Permutator( \"1 or Greater Required\" \)");
        }

        this.permutation = 0;

        // MAGIC NUMBER : 26 = Number of Letters in the English Alphabet 
        this.permutations = (int) Math.pow(26, LETTERS);

        this.stringbuilder = new StringBuilder();

        for (int i = 0; i < LETTERS; ++i) {
            this.stringbuilder.append('a');
        }
    }

    public String getCount() {

        return String.format("Permutation: %s of %s Permutations.", this.permutation, this.permutations);
    }

    public int getPermutation() {

        return this.permutation;
    }

    public int getPermutations() {

        return this.permutations;
    }

    private void permutate() {

        // TODO: Implement Utilising one of the Examples Posted.
    } 

    public String toString() {

        this.permutate();

        return this.stringbuilder.toString();
    }
}

Answer 7

you can use big integer's toString(radix) method like:

import java.math.BigInteger;
public class Strings {
    Strings(final int digits,final int radix) {
     this(digits,radix,BigInteger.ZERO);
    }
    Strings(final int digits,final int radix,final BigInteger number) {
     this.digits=digits;
     this.radix=radix;
     this.number=number;
    }
    void addOne() {
     number=number.add(BigInteger.ONE);
    }
    public String toString() {
     String s=number.toString(radix);
     while(s.length()<digits)
      s='0'+s;
     return s;
    }
    public char convert(final char c) {
     if('0'<=c&&c<='9')
      return (char)('a'+(c-'0'));
     else if('a'<=c&&c<='p')
      return (char)(c+10);
     else throw new RuntimeException("more logic required for radix: "+radix);
    }
    public char convertInverse(final char c) {
     if('a'<=c&&c<='j')
      return (char)('0'+(c-'a'));
     else if('k'<=c&&c<='z')
      return (char)(c-10);
     else throw new RuntimeException("more logic required for radix: "+radix);
    }
    void testFix() {
     for(int i=0;i<radix;i++)
      if(convert(convertInverse((char)('a'+i)))!='a'+i)
       throw new RuntimeException("testFix fails for "+i);
    }
    public String toMyString() {
     String s=toString(),t="";
     for(int i=0;i<s.length();i++)
      t+=convert(s.charAt(i));
     return t;
    }
    public static void main(String[] arguments) {
     Strings strings=new Strings(8,26);
     strings.testFix();
     System.out.println(strings.number.toString()+' '+strings+' '+strings.toMyString());
     for(int i=0;i<Math.pow(strings.radix,3);i++)
      try {
       strings.addOne();
       if(Math.abs(i-i/strings.radix*strings.radix)<2)
        System.out.println(strings.number.toString()+' '+strings+' '+strings.toMyString());
      } catch(Exception e) {
       System.out.println(""+i+' '+strings+" failed!");
      }
    }
    final int digits,radix;
    BigInteger number;
}

Answer 8

I'd have to agree with @saua's approach if you only wanted the final result, but here is a slight variation on it in the case you want every result.

Note that since there are 26^8 (or 208827064576) different possible strings, I doubt you want them all. That said, my code prints them instead of storing only one in a String Builder. (Not that it really matters, though.)

  public static void base26(int maxLength) {
    buildWord(maxLength, "");
  }
  public static void buildWord(int remaining, String word)
  {
    if (remaining == 0)
    {
      System.out.println(word);
    }
    else
    {
      for (char letter = 'A'; letter <= 'Z'; ++letter)
      {
        buildWord(remaining-1, word + letter);
      }
    }
  }

  public static void main(String[] args)
  {
    base26(8);
  }

Answer 9

The following code uses an "inductive" next() method to get the next string (let's say, from "aaaa" to "aaab" and so on) without the need of producing all the previous combinations, so it's rather fast. Moreover this method is not bounded to any particular string dimension.

public class StringInc {
 public static void main(String[] args) {
   String s = "a";

   while(true) {
     System.out.println(s);

     s = next(s);
   }
 }

 public static String next(String s) {
   int length = s.length();

   char c = s.charAt(length - 1);

   if(c == 'z' && length == 1)
     return "aa";

   String root = s.substring(0, length - 1);

   if(c == 'z')
     return next(root) + 'a';

    c++;

    return root + c;
  }
}