CODEWITHSUNDEEP
javaarraysalgorithmrecursionchar
silverzx
silverzx

Reputation: 1249

Iterating through a character array in Java - improving algorithm

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..

Upvotes: 2

Views: 15534

Answers (1)

mklnwt
mklnwt

Reputation: 61

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

}

Upvotes: 2

Related Questions