[Mystrunner]

Hello, all!

I'm attempting to wrap my head around a somewhat... logically-difficult programming assignment for a Java course. I'm not looking for help with the actual code, per-se, but figuring out the program structure is wringing my brain out, so I figured I'd see if you folks might be able to point me right.

The assignment describes a series of eight variables, A-H, which can each have any one of a series of eight values. There are five equations given, along the lines of "A+C=H" and "B+A=E". The object of the assignment is to create a program that can sort through all the various combinations of variables & values until it comes across the correct combination for all the equations.

Thus far, I've three classes, a "Variable" class that stores the variable and value of that variable, an "Expression" class that stores three Variables, and has a method to determine if the three Variables fit any of the equations. Finally, I've got a "Launcher" class that contains the main method and makes the magic happen. It has several arrays, one containing eight Variables, another containing five Expressions, and one to contain all the possible values alongside an array that contains the eight characters.

So far, I know that I'm thinking to use a series of nested for loops in order to cycle through all the character letters, assigning them to the Variable object array... but I'm at a loss as to how to *also* cycle through the values at the same time. Does anyone have a general idea of what an algorithm to do this would look like? I've included my for loop below... thanks!

for (int i = 0; i < varAry.length; i++){
			//The whole point of this thing is to assign each variable every single value and test them, 
			// changing one variable at a time until you wind up with a solution that fulfills all the test conditions.
				for(int charA = 0;;charA++){
					varAry[i].setLetter(charAry[charA]);
					
					for(int charB = 0;;charB++){
						varAry[i].setLetter(charAry[charB]);
						
						for(int charC = 0;;charC++){
							varAry[i].setLetter(charAry[charC]);
							
							for(int charD = 0;;charD++){
								varAry[i].setLetter(charAry[charD]);
								
								for(int charE = 0;;charE++){
									varAry[i].setLetter(charAry[charE]);
									
									for(int charF = 0;;charF++){
										varAry[i].setLetter(charAry[charF]);
										
										for(int charG = 0;;charG++){
											varAry[i].setLetter(charAry[charG]);
											
											for(int charH = 0;;charH++){
												varAry[i].setLetter(charAry[charH]);
												
											}
											
										}
										
									}
								}
							}
						}
					}
				}
		}

[GregBrannon]

If I understand what you're thinking based on the code you've posted, it won't work. You're right, you can't make that connection from cycling through a list of char variable names to their values, unless there was a relationship between the variable names and their values. Probably not, and even if there was, it would be too much trouble.

So, why not put the 8 variable values in 8 arrays and plug the values from each of the 8 arrays into the 5 equations until you find a solution? It's not clear to me if each of the variables can be any of the 8 values at any time, or if the 8 values come as a matched set. Perhaps you could clarify.

For my own curiosity, can you show the values and the 5 equations?

[Mystrunner]

I definitely can! I was attempting the current method because that was part of the "proposed solution" the prof. let us examine briefly... but since it's definitely not working for me, I suppose another way wouldn't hurt.

Equations:
G + D = C
A + C = E
H + B = A
G + F = E
A + B = D

Variables: A, B, C, D, E, F, G, H
Values: 2, 5, 7, 9, 15, 16, 24, 31

[GregBrannon]

Okay, I'm starting to get it. So the variables have to be matched with the given set of values 1-to-1 to satisfy all of the equations resulting in 8! possibilities.

Thinking . . .

[Mystrunner]

Oh, and I just realized you'd asked another question: once a value has been used, it shouldn't be used by any other variable (at least, that's what the prof says, and he's probably right. ). Thanks for the help with this. I can't seem to think my way out of this one...

[GregBrannon]

Yes, that's why 8! possible permutations. You can find a more complete explanation on Wikipedia, but a quick and dirty is:

If one of the 8 values is assigned to variable A, there are 7 remaining values that can be assigned to B. After assigning a value to B, 6 remain to be assigned to C, etc. So there are 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 or 8! permutations.

Solution approaches:

If you were schooled in advanced matrix math, you could write a set of matrices that could be used to solve the 5 equations for the 8 unknowns taken 3 at a time. Probably not.

The speed and programmability of the computer lends itself to a brute force solution which tries all 8! permutations until the solution is found. So the clever bit of the brute force solution is assigning the 8 possible values to the variables in 8! ways.

Think on that.

[GregBrannon]

You've been thinking awfully quietly.

Finding permutations is not a trivial exercise, and it's a good use for a recursive method. You can find examples on the web that may not fit your use exactly but could be relatively easily modified for your needs.

Permutations can be done "in order" or "out of order." The definitions likely vary, but in-order permutations are what we typically think of first:

2 5 7 9
2 5 9 7
2 7 5 9
2 7 9 5
2 9 5 7
2 9 7 5
5 2 7 9

etc. . .

For in-order permutations, a rough outline is:

// int[] result is an array of the same number of elements
// as the number being permuted, elements initialized to zero
permute( int[] result, int[] toPermute )
{
    // if toPermute.length == 0, done:
       // return and check resulting array

    // else, for i = 0 to toPermute.length:

    // here's the recursion:
    // permute( result, ( the subArray from( toPermute[0] to
    // toPermute[i] +  the subArray from( toPermute[i + 1] to
    // toPermute.length )
}

Methods to write in the above include subArray() and sumArrays().

Thanks for posting the question.

[Mystrunner]

Heh, sorry Greg! I've been at work, thinking about what you'd said, and fiddling with it when I could. I'll take a look at this, and do some research on permutations!