4
$\begingroup$

I have a matrix in this case of 3x11, but I want this to work for any dimension matrix. I want per row a column position on a non-zero value in that row, but that this value should be different than a column position already selected for another row. I also tried to solve it with a set of three lists and tried to get a sample from each list.

For example:

m = {{1, 2, 1, 1, 1, 1, 0, -1, -2, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 
  0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}}

A result would be {8,9,11} Even though position 8 is non-zero in the first and the second row/list, this position can be selected as long as a different position is chosen for the second row/list.

Preferentially the last positions (with the higher numbers) should be selected.

$\endgroup$

1 Answer 1

5
$\begingroup$

We construct an edge list from m using SparseArray and use FindIndependentEdgeSet to get the desired result.

For the "preferentially the last positions (with the higher numbers) should be selected" part, for each edge v1 -> v2 we use v2 as the edge weight.

ClearAll[edges]
edges[m_] := DirectedEdge[{a, #[[1]]}, {b, #[[2]]}] & /@ SparseArray[m]["NonzeroPositions"];
FindIndependentEdgeSet[edges[m], EdgeWeight -> {e_ :> e[[-1, -1]]}][[All, -1, -1]]

{8, 9, 11}

To make the last positions as small as possible we can use 1 / v2 as the edge weight for edge v1 -> v2:

FindIndependentEdgeSet[edges[m], EdgeWeight -> {e_ :> 1 / e[[-1, -1]]}][[All, -1, -1]]

{1, 7, 10}

An alternative approach is to use constrained optimization:

indices = SparseArray[m]["NonzeroPositions"];
vars = xx @@@ indices;
objective = vars.(Last /@ vars);
constraints = Join[Thread[0 <= vars <= 1], 
     Values@GroupBy[vars, First, Total[#] == 1 &], 
     Values@GroupBy[vars, Last, 0 <= Total[#] <= 1 &]];
argmax = ArgMax[{objective, constraints}, vars];
Pick[indices, argmax, 1]

{{1, 9}, {2, 8}, {3, 11}}

Change ArgMax to ArgMin to make the second positions as small as possible:

argmin = ArgMin[{objective, constraints}, vars];
Pick[indices, argmin, 1]

  {{1, 1}, {2, 7}, {3, 10}}

$\endgroup$
4
  • $\begingroup$ Thanks! It works :) $\endgroup$
    – Alice
    Jun 15, 2019 at 9:49
  • $\begingroup$ @Alice, my pleasure. Welcome to mma.se. $\endgroup$
    – kglr
    Jun 15, 2019 at 9:51
  • 1
    $\begingroup$ MaximalBy[#, Total]& seems to work as well in place of InternalListMin`. $\endgroup$ Jun 15, 2019 at 16:53
  • $\begingroup$ @Anjan, great idea; thank you. $\endgroup$
    – kglr
    Jun 15, 2019 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.