Cluster analysis - Unweighted pair-group average
Clustering is a task of grouping a set of objects in such a way that the objects in the same class are similar to each other and the objects in different classes are distinct. Cluster analysis is employed in many fields such as machine learning, pattern recognition, image analysis, etc.
In this kata, your task is to implement a simple clustering technique called 'Unweighted pair-group average'. This method takes a set of 2D points and the desired number of final clusters. Initially, each point forms its own cluster. The most similar (least distant) clusters are iteratively merged until the target number of clusters is reached.
The distance metric between two clusters is defined as the average distance between all pairs of points from the two clusters. For example: 
```
Cluster 1: (0, 0), (0, 1)
Cluster 2: (4, 3)
Distance = (sqrt((0-4)^2 + (0-3)^2) + sqrt((0-4)^2 + (1-2)^2)) / 2
```
Input:
- ```points``` - a list of 2D points ```[(1, 1), (3, 5), (4, 4), (8, 2), (0, 1)]```
- ```n``` - the desired number of clusters
Output:
- list of clusters, each cluster is a list of points
- points in each cluster should be sorted in ascending order
- the list of clusters should also be sorted in ascending order
Example:
- ```cluster(3, [(1, 1), (3, 5), (4, 4), (8, 2), (0, 1)])```
- should return 
```[ [(0, 1), (1, 1)],
     [(3, 5), (4, 4)],
     [(8, 2)]
   ]
```
Notes:
- the coordinates ```(x, y)``` are chosen from interval ```<0, 1000>```
- ```0 < len(points) <= 100```
- ```0 < n <= len(points)```
- there is always only one unique solution
- there are no duplicate points in the input
import math
import numpy as np
import itertools

def cluster(points, n):
    
    def get_cluster_distance(cluster1, cluster2):
        
        # function to find distance between a single pair
        def get_point_distance(coord_1, coord_2):
            x1, y1 = coord_1
            x2, y2 = coord_2
            return math.sqrt( ((x1 - x2)**2) + ((y1 - y2)**2) )
        
        distances = []
        for point_i in cluster1:
            for point_j in cluster2:
                distances.append(get_point_distance(point_i, point_j))
        
        return np.mean(distances)
        
    # Initiate list of all clusters, initially every point is a cluster (its own list)
    all_clusters = [[point] for point in points]
    
    # Main function
    while len(all_clusters) > n:
        distances = []
        for i, j in itertools.combinations([ _ for _ in range(len(all_clusters))], 2):
            distances.append([i, j, get_cluster_distance(all_clusters[i], all_clusters[j])])
        minimum_distance_pair = min(distances, key = lambda x:x[2])
        i, j, distance = minimum_distance_pair
        all_clusters[i] = all_clusters[i] + all_clusters.pop(j)
        
    # Sort points in each cluster
    for i in range(len(all_clusters)):
        all_clusters[i] = sorted(all_clusters[i])
    # Sort each cluster
    return sorted(all_clusters)
import math
import numpy as np
import itertools

def cluster(points, n):
    
    def get_cluster_distance(cluster1, cluster2):
        
        # function to find distance between a single pair
        def get_point_distance(coord_1, coord_2):
            x1, y1 = coord_1
            x2, y2 = coord_2
            return math.sqrt( ((x1 - x2)**2) + ((y1 - y2)**2) )
        
        distances = []
        for point_i in cluster1:
            for point_j in cluster2:
                distances.append(get_point_distance(point_i, point_j))
        
        return np.mean(distances)
        
    # Initiate list of all clusters, initially every point is a cluster (its own list)
    all_clusters = [[point] for point in points]
    
    # Main function
    while len(all_clusters) > n:
        distances = []
        for i, j in itertools.combinations([ _ for _ in range(len(all_clusters))], 2):
            distances.append([i, j, get_cluster_distance(all_clusters[i], all_clusters[j])])
        minimum_distance_pair = min(distances, key = lambda x:x[2])
        i, j, distance = minimum_distance_pair
        all_clusters[i] = all_clusters[i] + all_clusters.pop(j)
        
    # Sort points in each cluster
    for i in range(len(all_clusters)):
        all_clusters[i] = sorted(all_clusters[i])
    # Sort each cluster
    return sorted(all_clusters)