12
\$\begingroup\$

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]]
\$\endgroup\$
3
  • \$\begingroup\$ [[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? \$\endgroup\$
    – l4m2
    Feb 20, 2023 at 6:07
  • \$\begingroup\$ @l4m2 That is true; I will edit that. \$\endgroup\$
    – Yousername
    Feb 20, 2023 at 13:50
  • \$\begingroup\$ NB: I rolled back my attempt to improve the formatting. It was better on desktop but worse on mobile. \$\endgroup\$
    – Arnauld
    Feb 21, 2023 at 17:41

6 Answers 6

4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ What the hack is the real-world-usage of a language like this? \$\endgroup\$
    – swe
    Feb 21, 2023 at 7:03
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Feb 21, 2023 at 16:28
3
\$\begingroup\$

K (ngn/k), 51 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 45 44 bytes

I⊟⌊EΦEXηLθEηΦθ⁼λ﹪÷ιXηξη⌊ι⟦ΣEι∕ΣEλΣX⁻νλ²XLλ²ι

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

EXηLθEηΦθ⁼λ﹪÷ιXηξη

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

Φ...⌊ι

... where no cluster is empty...

E...⟦ΣEι∕ΣEλΣX⁻νλ²XLλ²ι

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

I⊟⌊...

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

\$\endgroup\$
3
\$\begingroup\$

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
}                        //
\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$
    – l4m2
    Feb 20, 2023 at 15:32
  • \$\begingroup\$ @l4m2 There was a bug indeed. Now fixed. Thank you! \$\endgroup\$
    – Arnauld
    Feb 20, 2023 at 15:58
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.