# Number Clusters

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 , 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]]

• [[8], [8, 8, 8]] or [[8, 8], [8, 8]] or [[8, 8, 8], [8]]  aren't [[8], [8, 8, 8]] and  [[8, 8, 8], [8]] same?
– l4m2
Feb 20, 2023 at 6:07
• @l4m2 That is true; I will edit that. Feb 20, 2023 at 13:50
• NB: I rolled back my attempt to improve the formatting. It was better on desktop but worse on mobile. Feb 21, 2023 at 17:41

# 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

• What the hack is the real-world-usage of a language like this?
– swe
Feb 21, 2023 at 7:03
• @swe A couple of reasons for creating esolangs are listed here. But to keep it short, I'd say the main goal is to have fun, and definitely not to address real-world usages. Feb 21, 2023 at 16:28

# K (ngn/k), 51 bytes

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


Try it online!

# 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$$

# 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
)                      //   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
}                        //

• If I don't get wrong, for f([8,10,11,12,13,15])(2), your output [ [ 12, 13, 15 ], [ 8, 10, 11 ] ] is 3.111111111111111, while [8],[12,13,15,10,11] is 2.96
– l4m2
Feb 20, 2023 at 15:32
• @l4m2 There was a bug indeed. Now fixed. Thank you! Feb 20, 2023 at 15:58

# 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!

# 05AB1E, 21 bytes

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


Try it online!

#### 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