Number Clusters

Question

Your task is to create a program or function, that when given an input list of nonnegative integers of length \$l \ge 2\$ and a nonnegative integer \$c\$ where \$2 \le c \le l\$, group the list into \$c\$ "clusters." What this means is, the average (population) variance* of all the groups should be as low as possible.

For example, [[0, 3], [4, 6]] has an average variance of \$\frac{\frac{\left(0-\frac{0+3}{2}\right)^2+\left(3-\frac{0+3}{2}\right)^2}{2}+\frac{\left(4-\frac{4+6}{2}\right)^2+\left(6-\frac{4+6}{2}\right)^2}{2}}{2}\$ or \$1.625\$, while [[0], [3, 4, 6]] has an average variance of \$\frac{\frac{\left(0-\frac{0}{1}\right)^2}{1}+\frac{\left(3-\frac{3+4+6}{3}\right)^2+\left(4-\frac{3+4+6}{3}\right)^2+\left(6-\frac{3+4+6}{3}\right)^2}{3}}{2}\$ or \$\frac{7}{9}\$, and \$\frac{7}{9} < 1.625\$, so the latter is the correct output for the first test case. The result will have the closest numbers placed together and the farthest numbers placed in different groups.

_{*This is calculated by squaring the distance between all the numbers in the list and the mean of it, and then taking the mean of those squared distances.}

Rules

• Groups and numbers inside of the groups can be in any order.
• When there are multiple possible outputs with the same average variance, any of them is acceptable.
• Each group must have at least one number.
• Input and output may be in any convenient format.
• This is code-golf, so the shortest answer in bytes wins.

Test Cases

Input                          Output (sorted)

[0, 3, 4, 6], 2                [[0], [3, 4, 6]]
[0, 1, 2, 3], 2                [[0, 1], [2, 3]]
[0, 1, 2, 3, 4], 2             [[0, 1], [2, 3, 4]] or [[0, 1, 2], [3, 4]]
[10, 13, 6, 11, 8], 3          [[6, 8], [10, 11], [13]]
[4, 2, 9], 3                   [[2], [4], [9]]
[1, 19, 8, 12, 3, 19], 3       [[1, 3], [8, 12], [19, 19]]
[8, 8, 8, 8], 2                [[8], [8, 8, 8]] or [[8, 8], [8, 8]]

Answer 1

Vyxal, 17 bytes

søṖ'L⁰=;‡ƛṁ-²ṁ;∑∵

Try it Online!

s                 # sort
 øṖ               # all partitions
   '   ;          # filter by:
    L             #   length
      =           #   is equal to
     ⁰            #   last input
        ‡       ∵ # minimum by:
         ƛ    ;   #   map:
          ṁ-      #     subtract mean
            ²     #     square
             ṁ    #     mean
               ∑  #   sum

Answer 2

K (ngn/k), 51 bytes

{.y@*<+/'x''a*a:y-x''y@:='+z\&z=#'?'+!z|^y}{+/x%#x}

Try it online!

Answer 3

Charcoal, 45 44 bytes

Ｉ⊟⌊ＥΦＥＸηＬθＥηΦθ⁼λ﹪÷ιＸηξη⌊ι⟦ΣＥι∕ΣＥλΣＸ⁻νλ²ＸＬλ²ι

Try it online! Link is to verbose version of code. Explanation:

ＥＸηＬθＥηΦθ⁼λ﹪÷ιＸηξη

All permutations of the input list elements into c clusters...

Φ...⌊ι

... where no cluster is empty...

Ｅ...⟦ΣＥι∕ΣＥλΣＸ⁻νλ²ＸＬλ²ι

... calculate the doubled variance of each cluster...

Ｉ⊟⌊...

... output the clusters with the minimum.

Edit: Saved 1 byte by calculating the doubled variance using the last alternative variance formula for finite populations:

$$ \textrm{Variance(X)} = \frac{1}{2N^2} \cdot \sum_{i=1}^{N} \sum_{j=1}^{N} (x_i - x_j)^2 $$

Answer 4

JavaScript (ES7), 182 bytes

Expects (list)(c).

a=>m=c=>eval("for(q=c**a.length;p=a.slice(-c).map((_,j)=>a.filter((_,i)=>!(q/c**i%c^j))),q--;)p.some(A=>A.map(v=>s+=(v-eval(A.join`+`)/w)**2/w,w=A.length)=='',s=0)|s>m||(m=s,o=p);o")

Try it online!

Commented

This is a version without eval() for readability.

a =>                     // a[] = input list
m =                      // initialize m to a non-numeric value
c => {                   // c = number of clusters
  for(                   // main loop:
    q = c ** a.length;   //   start with q = c ** a.length
    p = a.slice(-c)      //   p[] = partition of length c
    .map((_, j) =>       //   for each value in p[] at index j:
      a.filter((_, i) => //     for each value in a[] at index i:
        !(               //       keep the value if
          q / c ** i % c //       floor(q / c ** i) mod c
          ^ j            //       is equal to j
        )                //
      )                  //     end of filter()
    ),                   //   end of map()
    q--;                 //   stop once q = 0 has been processed
  )                      //
  p.some(A =>            //   for each array A[] in p[]:
    A.map(v =>           //     for each value v in A[]:
      s += (             //       add to s:
        v -              //         v minus
        eval(A.join`+`)  //         the sum of all values in A[]
        / w              //         divided by w (the length of A[])
      ) ** 2 / w,        //       squared and divided by w again
      w = A.length       //       initialize w
    )                    //     end of map()
    == '',               //     trigger the some() if A[] was empty
    s = 0                //     start with s = 0
  )                      //   end of some(); if the result is falsy
  | s > m ||             //   and we don't have s > m:
    (m = s, o = p);      //     update the minimum and the output array
                         // (implicit end of for)
  return o               // return the output array
}                        //

Answer 5

JavaScript (Node.js), 195 bytes

f=([c,...x],n,L=P=x.slice(-n).map(_=>[]))=>1/c?L.map((_,i)=>f(x,0,L.map(x=>i--?x:[...x,c])))&&P:P=B(P)<B(L)?P:L;A=x=>x.map(t=>X+=++Y&&t,X=Y=0)+x?X/Y:1/0;B=L=>A(L.map(x=>A(x.map(v=>(v-A(x))**2))))

Try it online!

Answer 6

05AB1E, 21 bytes

{.œʒg²Q}ΣεDÅA-nÅA}O}н

Try it online!

Port of AndrovT's Vyxal answer.

Explanation

{.œʒg²Q}ΣεDÅA-nÅA}O}н  # Implicit input
{                      # Sort the first input
 .œʒ   }               # Filter its partitions by:
    g                  #  Length of list
     ²Q                #  Equals the second nput
        Σ          }н  # Minimum by:
         ε       }     #  Map:
           ÅA          #   Get mean
          D  -         #   Subtract
              n        #   Square
               ÅA      #   Get mean
                  O    #  Sum
                       # Implicit output