Is there an approach to take to find the largest product that is possible to be made, by only multiplying one and only one number from each row and column?
Or even a brute force way I can use in Matlab.
Attached problem is easy example
In this example i think (i may be wrong ) the answer would be (9*9*6*3)=1458
But is there a general method
>>8054823
9*9*7*4 is the biggest product.
How big are the biggest grids you're working with? Because for an n*n grid, there are n! possible products. So you could brute force calculate them all and then choose the maximum, assuming n is small enough.
>>8054823
9*9*7*4 is bigger
>>8054839
That's gotta be way too high.
Pick 1 from the first column. 4
Pick 1 from the second column (only 3 possible choices.
Pick 1 from 3 column (2 choices)
Pick only choice from last column.
Only 4*3*2 = 24 valid products
>>8054849
Thank you combinatorics
>>8054852
Which is 4! Fuck me
>>8054858
lol
>>8054818
My recommendation is to put all the numbers in a list. For the 4*4 case, this will be a list of length 16.
Next, find a way to generate all possible permutations of a group of n objects.
(This website may help??http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list)
For the 4*4 case, if you have the numbers {1,2,3,4}, then you would want a program whose output is (1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2),(1,4,2,3),(1,4,3,2),(2,1,3,4) ... (4,1,2,3) ... (4,3,2,1).
Now, take each of these 16 vectors, and add 0 to the first term, 4 to the second term, 8 to the third term, and 12 to the 4th term.
The resultant 16 vectors will each give you the four indices of one of your possible grid selections.
7*8*9*6 is the answer to this one surely?
Take logs and do
https://en.wikipedia.org/wiki/Hungarian_algorithm
>>8054818
Largest product possible is the product of the largest n numbers eligible which do not share row or column. So go through all elements of matrix, keeping track of largest n numbers and there indices i,j. For each element if its in the largest n numbers check if indices i and j are unique then replace (or not) in your list as necessary. This is closer to n^2 calculations than the various n! approaches in this thread, though it requires some modification for what happens if tie within row or column.
Put every item into an array and sort it using heap sort or mergesort.
While there is an unlocked row/col, pick the highest number in your sorted array that is in a unique row and column.
This should have a time complexity of O(nlogn)
How did I do?
>>8056249
*Unpicked not unlocked.
>>8054818
Rows and columns are interchangeable without affecting the maximum product, correct?
Now choose to maximise the first, top-left square. There are only 2 ways to do so, because there are only 2 nines.
We want to maximise, through rearrangement of rows and columns, the diagonal of (1,1)...(4,4).
It seems right, though I can't yet express this part in a satisfactory way, that (2,2) will be the 8, because if it was the second 9 (the one on the same row as the 8) then you're losing the 6 from the column that 9 is on, and we want that 6 to go with the 8 in our maximised diagonal, since 9,9,8,7 isn't possible.
(3,3) will be the 7 which isn't in the same column as the 9, and (4,4) is that top-right 6.
9x8x7x6 is the maximum.
If the part I haven't expressed properly could be sorted, that might lead to a generalisation of the process. But this might be relying on the fact that the higher numbers aren't duplicated very much in the example.
>>8054818
shitty code incoming, but it does the job
A = [3 4 1 6; 4 8 2 9; 7 6 7 5; 2 5 9 3];
p = perms(1:size(A,2));
v = zeros(1,4);
vmax = zeros(1,4);
for k = 1:size(p,1)
for i = 1:size(A,1)
v(i) = A(i,p(k,i));
end
if prod(v)>prod(vmax)
vmax = v;
end
end
vmax
prod(vmax)
The highest math I have to take in my EE major is linear algebra. What class would cover combinatorics? If Im not getting boned by my major classes Id really like to take further maths. Not necessarily harder, but interesting topics
