0

I would like to compute a table with values in "every possible way" by multiplying one value from each column to a product. I would preferably solve the problem in Java. The table is of size n*m. It could for example be of size 3*5 and containing:

0.5, 3.0, 5.0, 4.0, 0.75
0.5, 3.0, 5.0, 4.0, 0.75
0.5, 9.0, 5.0, 4.0, 3.0

One way of getting the product would be:

0.5 * 3.0 * 5.0 * 4.0 * 0.75

How do I compute this in "every possible way" when the table is of size n*m? I would like to write one program (presumably containing loops) that works for every n*m table.

David Lindahl
  • 63
  • 9
  • 9
    Add some loops. – Dan W Jun 13 '13 at 21:09
  • Yeah, I know. But, the difficult part (at least for me) is doing this when the table is of random size. I.e. I would like to write a program that solve this problem for every size. – David Lindahl Jun 13 '13 at 21:10
  • you could just use an `ArrayList` and make your life easier – 0x6C38 Jun 13 '13 at 21:11
  • `ArrayList` + `Iterator`. – noMAD Jun 13 '13 at 21:12
  • 1
    Do you also mean diagonal computations? – fge Jun 13 '13 at 21:12
  • Also, what are the types of your elements? Are they `double`s? If yes you will potentially lose a _lot_ of precision – fge Jun 13 '13 at 21:13
  • I think you should give a bit more detail on what exactly "every possible way" means. I doubt whoever is asking you to do this literally wants every possible way to multiply numbers in that table. Is it every possible combination of one (only one) value from each column multiplied by one (only one) value from every other column? – Josh Jun 13 '13 at 21:15
  • What is your final goal of trying every possible way? Sometimes it is not necessary to enumerate all possible combinations such as finding the greatest resulting multiplication ... – keelar Jun 13 '13 at 21:15
  • @Josh I mean only one value from each column. Keelar: I would like to find the biggest product in the end. fge: they are double. – David Lindahl Jun 13 '13 at 21:18

2 Answers2

0

Create a recursive method that makes two calls, one call where you use a number in a column in the final product, and one call where you do not. In the call where you do not use it, you make two more calls, one where you use the next number in the column and one where you do not and so on. When you do use a number, you go to the next column, efficiently making a recursive tree of sorts where each leaf is a different combination of finding the product.

You would not need any data structure for this besides your table and it would be able to take in any size of table. If you do not understand the method I have described I can provide some short example code but it is fairly simple.

method findProducts(int total, pos x, pos y) 
if(inbounds of table)
findProducts(total + column[x]row[y] value, 0, y+1) 
findProducts(total, x+1, y) 
else 
print(total)

Something like this, a counter would be useful so you could only print those values that are combinations of y numbers, the amount of rows.

PandaBearSoup
  • 699
  • 3
  • 9
  • 20
  • Yes, that seems to be one way of doing it. But, I have very little experience with recursive algorithms. Would you like to give some further explanation? I would appreciate it very much! – David Lindahl Jun 13 '13 at 21:21
  • Sure, there is a finite number of combinations depending on the size of the table. Recursion becomes easier if you can visualize what you are doing. Imagine a tree where the root is .5, the first value in your table. On the left side of the tree is all the combinations of products where we dont use that value .5. On the right side is every combination where we do use it. Therefore, on the right side we move to the next column and repeat the process. On the leftside we move to the next row in that column and repeat. I will provide some pseudo code in my next post. – PandaBearSoup Jun 13 '13 at 21:28
  • Thank you for the further explanation! I will see if I can solve the problem now. – David Lindahl Jun 13 '13 at 21:46
0

You could do it recursively, as the other answer mentioned, but in general I find Java is somewhat unhappy with recursion. One other method to do it would be to keep track of a "signature" of where you are in the table (i.e., an array of length m where each value is 0 <= val < m). Each signature uniquely specifies a path through the table, and you can compute the value from a given signature pretty easily:

double val = 1.;
for (int j=0; j<m; j++)
     val *= table[j][signature[j];

To iterate through all signatures, think of them as (up to) m-digit numbers in base n and simply increment through, making sure to carry when you get above n. Here's some untested, unoptimized, probably badly indexed sample code:

int[] sig = new int[m];
double[] values = new double[m*n];
while (sig[m-1] < n) {
     values = getValue(table, sig);
     int carry = 1, j = 0;
     while (carry > 0 && j < n) {
         sig[j] += carry;
         carry = 0;
         while (sig[j] >= n) {
              sig[j] -= n;
              carry += 1;
         }
      }
 }
chessbot
  • 436
  • 2
  • 11