title: Python sequence cluster exercise
body: <p>I am working through an exercise in my textbook and am implementing the code in Python to practice dynamic programming. I feel like I am right on the edge of figuring it out, but after many hours, I come here for help. </p>
  
  <p>Basically my code is going through a list of values <code>x</code>, and given a <code>k</code>, break that list into <code>k</code> clusters based on calculating the minimum sum of squared errors (SSE) for a particular cluster.</p>
  
  <p>The code creates a table, calculating the SSE for 1 cluster, 2 clusters, ..., k clusters, if we were to put the cluster parentheses around all variations of values within <code>list[0:1]</code>, <code>list[0:2]</code>, <code>list[0:3]</code>, ..., <code>list[0:n]</code>, and choosing the minimum SSE for that particular step in the table.  </p>
  
  <p>For example: Given <code>x= [7,6,9,15,18,17,30,28,29]</code> and <code>k=3</code>, we would return clusters <code>(7,6,9)(15,18,17)(30,28,29)</code>, which would translate to sum of squared error equal to <code>(4.666)(4.666)(2)</code> for each cluster. So our max SSE would be <code>4.666</code> for that clustering on that list. </p>
  
  <p>Now when I try it on my second list <code>x = [52, 101, 103, 101, 6, 5, 7]</code>, I should get clustering <code>(52)(101, 103, 101)(6, 5, 7)</code>, which should give <code>(0)(2.666)(2)</code> or a max of <code>2.666</code>, but am not getting that. I believe the error lives in the  <code>def f(s, j_down, t)</code> for the 2nd return statement, and how I increment <code>s</code> and <code>t</code>. Hopefully I have not made a silly mistake!</p>
  
  <p>Any help is much appreciated, thank you. </p>
  
  <pre><code>def mean(numbers):
      return float(sum(numbers)) / max(len(numbers), 1)
  
  def sum_square(x):
      if isinstance(x, (int,)):
          return 0
      w = 0
      for i in x:
          w += (i - mean(x))**2
      return w
  
  def f(s, j_down, t):
      if not r[s][j_down] and r[s][j_down] != 0:
          return sum_square(x[:t - s])
  
      return max(r[s][j_down], sum_square(x[:t-s]))
  
  def get_min_f_and_s(j_down, t):
      """ range s from 1 to t-1 and set s to minimize f(s)
      """
      items = [(s, f(s, j_down, t)) for s in range(t)]
      s, min_f = min(items, key=lambda x:x[1])
      return s, min_f
  
  def seq_out(n,k):
      for j in range(k):
          if j == 0:
              for t in range(n):
                  r[t][j] = sum_square(x[:t+1])
  
                  c[t][j] = x[:t+1]
          else:
              for t in range(1, n):
                  s, min_f = get_min_f_and_s(j - 1, t)
                  r[t][j] = min_f
                  c[t][j] = [c[s][j - 1]] + x[s+1:t+1]
  
      print('the max SSE is: {}'.format(r[-1][-1]))
      print('the cluster centers are: {}'.format(c[-1][-1]))
  
  #x = [7,6,9,15,18,17,30,28,29]    
  x = [52, 101, 103, 101, 6, 5, 7]
  k = 3
  n = len(x)
  
  r = [[[] for _ in range(k)] for _ in range(n)]
  c = [[[] for _ in range(k)] for _ in range(n)]
  
  print(seq_out(n,k))
  print(r)
  print(c)
  </code></pre>
  
  <p>Edit: Question layout</p>
  
  <p>Given a sequence <code>X = [x_1, x_2, ... x_n]</code> and integer <code>k &gt; 1</code>, partition <code>X</code> into clusters <code>C_1,..., C_k</code> of sizes <code>n_1, ..., n_k</code>, so that the sum of squared errors is minimized. </p>