CODEWITHSUNDEEP
javaarraysfor-loopwhile-loop
dollaza
dollaza

Reputation: 213

combinatorics with string array

I found a solution that prints all combinations of a string. The code below would have an output of:

Toyota black sedan
Honda black sedan
Toyota red sedan
Honda red sedan
Toyota black suv
Honda black suv
Toyota red suv
Honda red suv 

String[][] sets = new String[][] {{"Toyota", "Honda"}, {"black", "red"}, {"sedan", "suv"}};
int[] state = new int[sets.length];
int p = 0;
while (true) {
    for (int i = 0; i < state.length; i++) {
        System.out.print(sets[i][state[i]] + " ");
    }

    System.out.println();
    state[p]++;

    while(state[p] == sets[p].length) {
        state[p] = 0;
        p++; 
        if (p == sets.length) return;
        state[p]++;
    }
    p = 0;  
}

Can someone please elaborate and explain what the second while loop is doing?

Upvotes: 1

Views: 117

Answers (1)

ajb
ajb

Reputation: 31699

state is being used here to simulate a multiply nested for loop. If you knew that there were 3 sets in sets, you could accomplish this with something like

for (int i = 0; i < sets[2].length; i++) {
    for (int j = 0; j < sets[1].length; j++) {
        for (int k = 0; k < sets[0].length; k++) {
             // form output from sets[0][k], sets[1][j], sets[2][i]
        }
    }
}

However, this doesn't work when you don't know how many indexes you'll need.

The state array in effect holds all the indexes of the nested for loops. state[0] is the innermost index (k in the above example), state[1] is the next innermost index (j), etc. This line (above the inner while loop):

state[p]++;

will increment state[0], since p must always be 0 at this point (I think it should have been written state[0]++ for clarity). Now we need to handle the indexes that have reached their limit, which is what the second while loop does:

while(state[p] == sets[p].length) {
    state[p] = 0;
    p++; 
    if (p == sets.length) return;
    state[p]++;
}

Starting with p==0, we see if state[0] has reached its limit (i.e. k==sets[0].length in the nested for example). If it has, we simulate exiting that for loop by resetting that index to 0 (ahead of time), then moving out to the next outer for loop. Now p==1, so we'll be incrementing state[1] which is j in the nested for example. state[p]++ increments j, then we go back to the top of the while loop to see if j has reached its limit. If so, we do the same thing--reset j to 0, then look at state[2] which is equivalent to i, and so on...

Upvotes: 1

Related Questions