title: How to divide N numbers into N/2 groups (2 numbers each group) such that the sum of diffrence between the 2 numbers in each group is minmal?
body: <h1>General Problem Description</h1>
  
  <p>Hi, it is actually a special <strong>assignment problem</strong>( check wiki if interested). Suppose I have 10 agents denoted as <em>A1, A2, ... A10</em> and I need them to work in pairs. While, according to previous experience, I know the working efficiency of each two-agent pair so that I have an efficiency matrix shown as follows whose <em>( i, j )</em> element represents the working efficiency of agent pair <em>( Ai, Aj )</em>. Hence, we know it should be a symmetric matrix, which means <em>E( i, j )=E( j, i )</em> and <em>E( i, i )</em> should be 0. Now, I need divide these 10 agents into 5 groups such that the overall (sum) efficiency is maximal.</p>
  
  <p>E =</p>
  
  <pre><code> 0    25    28    23    39    77    56    58    85    41
  25     0    18    77    32    52    69    59    47    18
  28    18     0    20    55    75    63    38     5    56
  23    77    20     0    59    76    24    82    68    64
  39    32    55    59     0    49    70    28    42    31
  77    52    75    76    49     0    33    84    50    29
  56    69    63    24    70    33     0    15    49    83
  58    59    38    82    28    84    15     0    68    40
  85    47     5    68    42    50    49    68     0    56
  41    18    56    64    31    29    83    40    56     0
  </code></pre>
  
  <h1>N.B.</h1>
  
  <ol>
  <li>From the matrix view of this problem, I need pick 5 elements from above matrix such that none of them share a same index with others. ( if you pick <em>E( 2, 3 )</em>, then you cannot pick any elments with index containing 2 or 3 since <em>A2</em> and <em>A3</em> are assigned to work. In other words, you cannot pick any elements from the 2nd, 3rd row and 2nd, 3rd column.)</li>
  <li>The title of this problem is an equivalent problem to the special assignment problem mentinoned above.</li>
  <li>You may find the <a href="https://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow">Hungarian(munkres) algorithm</a> helpful! <a href="http://www.mathworks.com/matlabcentral/fileexchange/20328-munkres-assignment-algorithm" rel="nofollow">Here</a> is the <strong>matlab</strong> code.</li>
  <li>Another view of this problem is to solve a normal assignment problem, but we need to find a solution whose elements are symmetrically distributed about the diagonal.</li>
  <li>Directly applying Hungarian(munkres) algorithm to the symmetric efficiency matrix does not always work. Sometimes it will give asymmetric permutations e.g.</li>
  </ol>
  
  <p>E =</p>
  
  <pre><code> 0    30    63    32    20    40
  30     0    67    84    75    63
  63    67     0    37    79    88
  32    84    37     0    43    59
  20    75    79    43     0    56
  40    63    88    59    56     0
  </code></pre>
  
  <p>The optimal solution is:</p>
  
  <p>assignment =</p>
  
  <pre><code> 0     0     0     0     0     1
   0     0     0     1     0     0
   1     0     0     0     0     0
   0     1     0     0     0     0
   0     0     1     0     0     0
   0     0     0     0     1     0
  </code></pre>