Selecting unique column position of a non-zero value for each row of a matrix

Question

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.

Answer 1

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}}