1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Matrix puzzler

  1. Oct 5, 2012 #1
    I'd like to find a simple algorithm to do the following.

    If I have an NxM matrix, with N≥M, find the M entries with the maximum product that do not share a row or column.

    It doesn't seem hard, but I'm not seeing it right off.
  2. jcsd
  3. Oct 5, 2012 #2


    User Avatar
    Science Advisor

    Hey Chuck37.

    I've never heard of the maximum product: can you outline what this corresponds to?
  4. Oct 5, 2012 #3
    Wait, do you mean the maximum product as simply the result of multiplying the greatest non-intersecting plots of a MN matrix? Just to clarify

    For example, in the 6-schematized matrix:

    (1) (2)
    (3) (4)
    (5) (6)

    the maximum product would be (5)(4) = 20 etc.
  5. Oct 6, 2012 #4


    User Avatar
    Science Advisor

    I'm not sure what it physically corresponds to, but it sounds like an interesting problem. :smile:

    Well let's start with brute force. If N,M are not too large you could try all [itex]\frac{n!}{(n-m)!}[/itex] combinations.

    There might be a nice neat algorithm that does this really cleanly, but if that "ideal" algorithm can't be found then modifying brute force to add heuristics might work out ok.
  6. Oct 6, 2012 #5


    User Avatar
    Science Advisor
    Homework Helper

    This sems a very hard problem if the matrix entries can be either positive or negative, because a positive maximum value might involve some negative elements of the matrix. It's hard to see how to solve that except by brute force.

    If you want to think about more efficient searching strategies, it would probably be better to restruct the problem to positive numbers.
  7. Oct 9, 2012 #6
    Sorry I'm just getting back to this after the weekend. The values inside are probabilities and thus always positive. I have brute force currently implemented, but when the matrix gets big, there are a lot of combinations and since I have to do it a lot, it adds up.

    Maximum product was intended just how it sounds, the N entries that when multiplied together give the biggest values - with no entries sharing a row or column (the example from Alcatrace IV is right). At this point I'd be happy with something that is close most of the time since I need speed.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook