title: Fastest python algorithm to divide a list of numbers into N groups that maximizes the total mean differences of every two closest groups
body: <p>Say I have a list of integers</p>
  <pre><code>[1, 107, 1010, 3, 121, 5, 1024, 118, 101, 1, 123, 1357]
  </code></pre>
  <p>I want to divide them into N=3 groups (not necessarily equal in length), meanwhile maximize the total differences between the mean values of every two closest groups. This is an extreme example, the expected partition is obviously</p>
  <pre><code>res = [[1, 3, 5, 1],
         [107, 121, 118, 101, 123],
         [1010, 1024, 1357]]
  </code></pre>
  <p>I use the following function to calculate the total differences between the mean values of every two closest groups</p>
  <pre><code>import numpy as np
  
  def calc_mean_diff_sum(list_of_lists):
      list_of_lists.sort(key=lambda x: np.mean(x))
      return np.sum([np.mean(list_of_lists[i+1]) - np.mean(group)
                     for i, group in enumerate(list_of_lists[:-1])])
  
  print(calc_mean_diff_sum(res))
  &gt;&gt;&gt; 1127.8333333333333
  </code></pre>
  <p>However, how should I divide a list of 12 random numbers into 3 groups?</p>
  <pre><code>a = np.random.rand(12,)
  </code></pre>
  <p>Right now I am using brute force enumeration of all possible partitionings and choose the one that maximizes the <code>calc_mean_diff_sum</code> function, but I think there must be some faster algorithms out there. Any suggestions?</p>
  <p>I want to say this question has further implication of a clustering problem based on similarities.</p>