Iterating through a character array in Java - improving algorithm

Question

I'm trying to iterate through my array to produce all possible combinations of the given char array.

If the length I specify is 4 then I want it to iterate through all combinations of the chars in the array up to a length of 4.

It would look something like this:

char[] charArray = "abcdefghijklmnopqrstuvwxyz".toCharArray();

Output of method I want:

a, b, c, ..., x, y, z, aa, ab, ac, ..., ax, ay, az, ba, bb, bc, ..., bx, by, bz, ca, cb, cc, ... zzzx, zzzy, zzzz

Here's some code:

cs = charArray;
cg = new char[4]; // 4 up to 4 characters to guess

int indexOfCharset = 0; // should I be using all these?
int indexOfCurrentGuess = 0;
int positionInString = 0;

public void incrementNew() {
    // 1 DIGIT guesses
    if (cg.length == 0) {
        if (indexOfCharset == cs.length) {
            cg = new char[cg.length + 1];
        } else {
            cg[positionInString] = nextChar();
        }
    }
    // 2 DIGIT guesses
    else if (cg.length == 1) {
        if (cg[0] == cs.length && cg[1] == cs.length) {
            cg = new char[cg.length + 1];
        } else {
            ... Something goes here <-
            cg[positionInString] = nextChar();
        }
    }
    System.out.println("cg[0]=" + cg[0]);
}

public char nextChar() {
    char nextChar;
    if (indexOfCharset < cs.length) {
        nextChar = cs[indexOfCharset];
    } else {
        indexOfCharset = 0;
        nextChar = cs[indexOfCharset];
    }
    indexOfCharset++;
    //System.out.println("nextChar = " + nextChar);
    return nextChar;

}

The only way I can think of doing it is using lots of IF statements - is there an algorithm or way to do it neater? If not then any suggestions on how to deal with two or more characters?

EDIT:

I want it to work for any unsorted char arrays not just a-z.

All the implementations I've found only work for sorted arrays..

I think the code in this answer: "[Brute Force Algorithm w/Java Passing String Error](http://stackoverflow.com/questions/15046796/brute-force-algorithm-w-java-passing-string-error/15046867#15046867)" is exactly what you are looking for. You would have to change one line in the main method to `BruteForceIterator bit = new BruteForceIterator('a', 'z', 4);` — jlordo, Mar 07 '13 at 11:47
You want a [Power set](http://en.wikipedia.org/wiki/Power_set), try [this](http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java). — Boris the Spider, Mar 07 '13 at 11:54
What if I wanted numbers and lower case letters? Also it doesn't work if I change the order of the char set. I want it to deal with any char set. E.g. letters, numbers, characters. Not just A-Z. — silverzx, Mar 07 '13 at 12:01

mklnwt · Accepted Answer · 2013-03-07T12:50:48.447

2

You could try this:

static char[] letters = "abcdefghijklmnopqrstuvwxyz".toCharArray();

static void getChars(char[] lastChars, int pos, int length) {
    for (char c : letters) {
        char[] newChars = lastChars.clone();
        newChars[pos] = c; // if you have "aa" for example and the current length is 4. If c = "a", newChars is now "aaa"
        if (pos + 1 < length) { // as your lenths is 4 and you still have only 3 letters, getChars adds the missing ones
            getChars(newChars, pos + 1, length);
        } else {
            System.out.println(newChars);
        }
    }
}

public static void main(String[] args) {
    int maxLength = 4;

    for (int length = 1; length <= maxLength; length++) {
        for (char c : letters) {
            if (length > 1) {
                char[] chars = new char[length];
                chars[0] = c;
                getChars(chars, 1, length);
            } else {
                System.out.println(c);
            }
        }
    }

}

edited Mar 07 '13 at 12:50

answered Mar 07 '13 at 12:12

mklnwt

61
4

This is a recursive algorithm. For each length it builds the char arrays. The first letter is added in the main method. After that getChars adds one more char for each one in letters. If the limit of the current length is not reached, it calls getChars again to get the missing ones. – mklnwt Mar 07 '13 at 12:46
How would I go about breaking out of the for loop: for (char c : letters) { once its found the string I'm looking for? I've tried using a loop like innerloop: then break innerloop; I've also tried doing a while loop outside with a boolean that changes once the password has been found but it just ends up looping still! – silverzx Mar 07 '13 at 14:56
Also what does "for (char c : letters) {" do, can I add a condition to this like seen in this post: http://stackoverflow.com/a/7081497/1082213 – silverzx Mar 07 '13 at 15:38
A lot of questions. "for (char c : letters) {" iterates through any iterable (like and array). So every time it takes out the next element. You could use "for (int i = 0; i < letters.length [HERE YOU CAN ADD ADDITIONAL CONDITIONS (like "&& 1 != 2")]; i++) {". You can define a boolean before and change it, when your array is found. That way you could break out of the loop. – mklnwt Mar 07 '13 at 18:25

Iterating through a character array in Java - improving algorithm

1 Answers1