The assignment step of k-means: every point joins the cluster of its nearest centroid.
What to build
A program that assigns points on a line to their nearest centroid and counts each cluster's size.
Requirements
- Clusters are numbered from 1 in the order the centroids are given; a tie goes to the lower number.
- Print the cluster number of each point on one line, separated by spaces.
- Then print
sizesfollowed by the number of points in each cluster.
Input
Line 1: the centroids. Line 2: the points.
Output
Two lines.
Constraints
1 to 20 centroids; 1 to 1000 points.
Example
Input:
2 10
1 3 9 12 6
Output:
1 1 2 2 1
sizes 3 2
Why it works
Each point goes where its distance, and so its contribution to the inertia, is smallest, which is exactly what the assignment step needs.
Examples
Example 1 · Input
2 10 1 3 9 12 6
Expected output
1 1 2 2 1 sizes 3 2
Example 2 · Input
0 5 -5
Expected output
1 1 sizes 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each point, find the centroid with the smallest absolute difference.
Hint 2
On a tie, keep the centroid listed first.
Solution
Show one correct solution (try it yourself first)
centroids = list(map(float, input().split()))
points = list(map(float, input().split()))
labels = [min(range(len(centroids)), key=lambda k: (abs(p - centroids[k]), k)) + 1 for p in points]
print(*labels)
print("sizes", *[labels.count(k + 1) for k in range(len(centroids))])