title: Implementing Algorithm X in R
body: <p>I am looking to implement something sort of like <a href="https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="nofollow noreferrer">Knuth's Algorithm X</a> in R.</p>
  
  <p>The problem: I have a n x k matrix A, n>=k, with real-valued entries representing a cost. Both n and k are going to be pretty small in general (n&lt;10, k&lt;5). I want to find the mapping of rows onto columns that minimizes the total cost of the matrix, subject to the constraint that no single row can be used twice.</p>
  
  <p>I think this is sort of like Algorithm X in that a reasonable approach seems to be:</p>
  
  <ol>
  <li>Pick a column in A and find the minimum value in it.</li>
  <li>Remove that row and that column. Now you're left with Asub.</li>
  <li>Go to Step 1 and repeat with Asub, and a new column selection, until ncol(Asub)=1.</li>
  </ol>
  
  <p>But I can't figure out how to create a recursive data structure in R that will store the resulting tree of cell-level costs. Here's what I have so far, which only makes it down one branch, and so doesn't find the optimal solution.</p>
  
  <pre><code># This version of the algorithm always selects the first column. We need to make it 
  # traverse all branches.
  algorithmX &lt;- function(A) {
    for (c in 1:ncol(A)) {
      r &lt;- which.min(A[,c])
      memory &lt;- data.frame(LP_Number = colnames(A)[c], 
                           Visit_Number = rownames(A)[r], 
                           cost = as.numeric(A[r,c]))
      if (length(colnames(A))&gt;1) {
        Ared &lt;- A[-r, -c, drop=FALSE]
        return( rbind(memory, algorithmX(Ared)) )
      }
      else {
        return(memory)
      }
    }
  }
  
  foo &lt;- c(8.95,3.81,1.42,1.86,4.32,7.16,12.86,7.59,5.47,2.12,
           0.52,3.19,13.97,8.79,6.52,3.37,0.91,2.03)
  colnames(foo) &lt;- paste0("col",c(1:3))
  rownames(foo) &lt;- paste0("row",c(1:6))
  algorithmX(foo)
  </code></pre>
  
  <p>I'm sure I'm missing something basic in how to handle recursion in an R function. I'm also happy to hear other ways of solving this problem if this algorithm isn't actually the best fit.</p>