# Thread: Program Question

1. Member
Join Date
Jan 2011
Posts
2
Rep Power
0

## Program Question

I do not want to seem as if I just want an answer to a homework problem. But I just want to know what exactly I could do to write code to accomplish the task.

I am in a Java with Data Structures course and my professor gave me this:

Solve A/BC + D/EF + G/HI = 1 where A, B,C,... I are {1,2,3,...9} and each digit is used exactly once. Here BC, EF, HI are concatenations rather than multiplications. e.g. If B = 3 and C = 5, BC would be the number 35 (not the product 3x5 = 15). (The solution is unique up to ordering of the fractions.)

I would really appreciate some help.

Thanks,

Jim

2. Member
Join Date
Jan 2011
Posts
2
Rep Power
0
this is what i have so far:
Java Code:
```public class StringProblem {
public static void main(String[] args) {
double a = 1;
double d = 4;
double g = 7;
String b = "2";
String c = "3";
String e = "5";
String f = "6";
String h = "8";
String i = "9";
String first = b+c;
String second = e+f;
String third = h+i;
double bc = Integer.parseInt(first);
double ef = Integer.parseInt(second);
double hi = Integer.parseInt(third);
double answer = (a/bc) + (d/ef) + (g/hi);
}
}```

3. Originally Posted by WickedBetrayal
I do not want to seem as if I just want an answer to a homework problem. But I just want to know what exactly I could do to write code to accomplish the task.

I am in a Java with Data Structures course and my professor gave me this:

Solve A/BC + D/EF + G/HI = 1 where A, B,C,... I are {1,2,3,...9} and each digit is used exactly once. Here BC, EF, HI are concatenations rather than multiplications. e.g. If B = 3 and C = 5, BC would be the number 35 (not the product 3x5 = 15). (The solution is unique up to ordering of the fractions.)

I would really appreciate some help.

Thanks,

Jim
First let's get rid of those ugly divisions: your problem is equvalent to the problem: A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI. Variables A .. I are a permutation of the values 1 ... 9. We have to find a permutation such that the equality holds. The equation makes sense in mathematical notation as:

A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
(10*B+C)*(10*E+F)*(10*H+I)

(I hope I got that right ;-)

Finding permutations isn't a trivial task but very well doable. The next method finds a next permutation (if there is one) given a current permutation in lexicographical order. Let a current permutation be P0 P1 P2 ... Pn;

the steps are:

Java Code:
```1) find a largest i such that Pi < P(i+1)
2) if no such i exists there is no next permutation
3) find a largest j such that j > i and Pj > Pi (such a value j always exists)
4) swap values Pi and Pj
5) reverse the subsequence P(i+1) .. Pn```
Those five steps produce a next permutation given a curent one: P1 ... Pn.

You have to check all permutations starting at permutation 1, 2, 3 ... 9 and evaluate the equality above. If it holds you have found values for A ... I.

kind regards,

Jos
Last edited by JosAH; 01-09-2011 at 10:54 AM.

4. Member
Join Date
Jan 2011
Posts
9
Rep Power
0
I'm also having problems with this. I understand doing the A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI to get ride of the divisions. Could you explain how A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
(10*B+C)*(10*E+F)*(10*H+I) is equal to the other equation.

Also, the first step you said to do is find a largest i such that Pi < P(i+1). Does that mean I must increase all the variables by 1? How am I supposed to set up the first permutation? Do I just set A to 1, B to 2, and so on?

Sorry I'm very confused. I'd appreciate any help. Thank You.

5. Originally Posted by nve5009
I'm also having problems with this. I understand doing the A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI to get ride of the divisions. Could you explain how A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
(10*B+C)*(10*E+F)*(10*H+I) is equal to the other equation.
If e.g. BC == 12 then B == 1 and C == 2; so mathemaTically 10*B+C == 10*1+2 == 12. The first notation is a symbolic notation, while the second is a methematical notation.

Originally Posted by nve5009
Also, the first step you said to do is find a largest i such that Pi < P(i+1). Does that mean I must increase all the variables by 1? How am I supposed to set up the first permutation? Do I just set A to 1, B to 2, and so on?

Sorry I'm very confused. I'd appreciate any help. Thank You.
If you have a permutation, say, 14532, finding a largest i such that Pi < P(i+1) results in i == 1 because 4 < 5 and 4 is located at position 1. Next you have to find a largest j such that Pj > Pi. Pi == 4 and if j == 2 then Pj == 5 and 5 > 4. Swap Pi and Pj, so we get 15432 and next we have to reverse the subsequence starting at position i+1: 432, reversed we get 15234. Got it?

You do have to set up the first permutation yourself, which is easy: 123456789

kind regards,

Jos

edit: After rereading my own pseudo code I noticed that it was quite terse, so here is a Java implementation. This class permutes a char array with five elements:

Java Code:
```import java.util.Arrays;

public class T {

private static void swap(char[] s, int i, int j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
}

public static char[] permute(char[] s) {

int i, j;

for (i = s.length - 1; --i >= 0;)
if (s[i] < s[i + 1])
break;

if (i < 0)
return null;

for (j = s.length; --j > i;)
if (s[i] < s[j])
break;

swap(s, i, j);

for (j = s.length; ++i < --j;)
swap(s, i, j);

return s;
}

public static void main(String[] args) {

char[] names = "ABCDE".toCharArray();

do {
System.out.println(Arrays.toString(names));
} while (permute(names) != null);
}
}```
Last edited by JosAH; 01-13-2011 at 08:57 AM.

6. Member
Join Date
Jan 2011
Posts
9
Rep Power
0
thanks for the response. I think I understand what to do now. I'll post again if I have anymore problems but thanks a lot

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•