




import warnings

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.metrics import pairwise_distances

warnings.filterwarnings('''ignore''')

SCREAMING_SNAKE_CASE:    str											=   '''K-MEANS-CLUST/ '''


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase=None   )->  Optional[int]:







  if seed is not None:  # useful for obtaining consistent results
    np.random.seed(lowerCAmelCase   )
  SCREAMING_SNAKE_CASE_							=       data.shape[0]  # number of data points

  # Pick K indices from range [0, N).
  SCREAMING_SNAKE_CASE_							=       np.random.randint(0						,	lowerCAmelCase						,	lowerCAmelCase   )

  # Keep centroids as dense format, as many entries will be nonzero due to averaging.
  # As long as at least one document in a cluster contains a word,
  # it will carry a nonzero weight in the TF-IDF vector of the centroid.
  SCREAMING_SNAKE_CASE_							=       data[rand_indices, :]

  return centroids


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase   )->  Union[str, Any]:
  return pairwise_distances(lowerCAmelCase						,	lowerCAmelCase						,	metric='euclidean'   )


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase   )->  Dict:
  SCREAMING_SNAKE_CASE_							=       centroid_pairwise_dist(lowerCAmelCase						,	lowerCAmelCase   )

  # Compute cluster assignments for each data point:
  # Fill in the blank (RHS only)
  SCREAMING_SNAKE_CASE_							=       np.argmin(lowerCAmelCase						,	axis=1   )

  return cluster_assignment


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase   )->  List[str]:
  SCREAMING_SNAKE_CASE_							=       []
  for i in range(lowerCAmelCase   ):
    # Select all data points that belong to cluster i. Fill in the blank (RHS only)
    SCREAMING_SNAKE_CASE_							=       data[cluster_assignment == i]
    # Compute the mean of the data points. Fill in the blank (RHS only)
    SCREAMING_SNAKE_CASE_							=       member_data_points.mean(axis=0   )
    new_centroids.append(lowerCAmelCase   )
  SCREAMING_SNAKE_CASE_							=       np.array(lowerCAmelCase   )

  return new_centroids


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase   )->  Any:
  SCREAMING_SNAKE_CASE_							=       0.0
  for i in range(lowerCAmelCase   ):
    # Select all data points that belong to cluster i. Fill in the blank (RHS only)
    SCREAMING_SNAKE_CASE_							=       data[cluster_assignment == i, :]

    if member_data_points.shape[0] > 0:  # check if i-th cluster is non-empty
      # Compute distances from centroid to data points (RHS only)
      SCREAMING_SNAKE_CASE_							=       pairwise_distances(
          lowerCAmelCase						,	[centroids[i]]						,	metric='euclidean'   )
      SCREAMING_SNAKE_CASE_							=       distances**2
      heterogeneity += np.sum(lowerCAmelCase   )

  return heterogeneity


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase   )->  str:
  plt.figure(figsize=(7, 4)   )
  plt.plot(lowerCAmelCase						,	linewidth=4   )
  plt.xlabel('# Iterations'   )
  plt.ylabel('Heterogeneity'   )
  plt.title(F'''Heterogeneity of clustering over time, K={k:d}'''   )
  plt.rcParams.update({'font.size': 16}   )
  plt.show()


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase=500						,	lowerCAmelCase=None						,	lowerCAmelCase=False   )->  int:
  SCREAMING_SNAKE_CASE_							=       initial_centroids[:]
  SCREAMING_SNAKE_CASE_							=       None

  for itr in range(lowerCAmelCase   ):
    if verbose:
      print(lowerCAmelCase						,	end=''   )

    # 1. Make cluster assignments using nearest centroids
    SCREAMING_SNAKE_CASE_							=       assign_clusters(lowerCAmelCase						,	lowerCAmelCase   )

    # 2. Compute a new centroid for each of the k clusters, averaging all data
    #    points assigned to that cluster.
    SCREAMING_SNAKE_CASE_							=       revise_centroids(lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase   )

    # Check for convergence: if none of the assignments changed, stop
    if (
        prev_cluster_assignment is not None
        and (prev_cluster_assignment == cluster_assignment).all()
    ):
      break

    # Print number of new assignments
    if prev_cluster_assignment is not None:
      SCREAMING_SNAKE_CASE_							=       np.sum(prev_cluster_assignment != cluster_assignment   )
      if verbose:
        print(
            F'''    {num_changed:5d} elements changed their cluster assignment.'''   )

        # Record heterogeneity convergence metric
    if record_heterogeneity is not None:
      # YOUR CODE HERE
      SCREAMING_SNAKE_CASE_							=       compute_heterogeneity(lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase   )
      record_heterogeneity.append(lowerCAmelCase   )

    SCREAMING_SNAKE_CASE_							=       cluster_assignment[:]

  return centroids, cluster_assignment


# Mock test below
if False:  # change to true to run this test case.
      from sklearn import datasets as ds

      SCREAMING_SNAKE_CASE:    Union[str, Any]											=   ds.load_iris()
      SCREAMING_SNAKE_CASE:    Dict											=   3
      SCREAMING_SNAKE_CASE:    Union[str, Any]											=   []
      SCREAMING_SNAKE_CASE:    List[str]											=   get_initial_centroids(dataset['''data'''], k, seed=0)
      SCREAMING_SNAKE_CASE							,				SCREAMING_SNAKE_CASE:    Dict											=   kmeans(
          dataset['''data'''],
          k,
          initial_centroids,
          maxiter=4_0_0,
          record_heterogeneity=heterogeneity,
          verbose=True,
      )
      plot_heterogeneity(heterogeneity, k)


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase						,	lowerCAmelCase=None   )->  Optional[Any]:







  if fill_missing_report:
    SCREAMING_SNAKE_CASE_							=       df.fillna(value=lowerCAmelCase   )
  SCREAMING_SNAKE_CASE_							=       1
  SCREAMING_SNAKE_CASE_							=       df.select_dtypes(np.number   ).columns
  SCREAMING_SNAKE_CASE_							=       (
      df.groupby(['Cluster']   )[  # construct report dataframe
          numeric_cols
      ]  # group by cluster number
      .agg(
          [
              ('sum', np.sum),
              ('mean_with_zeros', lambda lowerCAmelCase   : np.mean(np.nan_to_num(lowerCAmelCase   )   )),
              ('mean_without_zeros', lambda lowerCAmelCase   : x.replace(0						,	np.NaN   ).mean()),
              (
                  'mean_25-75',
                  lambda lowerCAmelCase   : np.mean(
                      np.nan_to_num(
                          sorted(lowerCAmelCase   )[
                              round(len(lowerCAmelCase   ) * 25 / 100   ) : round(len(lowerCAmelCase   ) * 75 / 100   )
                          ]   )   ),
              ),
              ('mean_with_na', np.mean),
              ('min', lambda lowerCAmelCase   : x.min()),
              ('5%', lambda lowerCAmelCase   : x.quantile(0.0_5   )),
              ('25%', lambda lowerCAmelCase   : x.quantile(0.2_5   )),
              ('50%', lambda lowerCAmelCase   : x.quantile(0.5_0   )),
              ('75%', lambda lowerCAmelCase   : x.quantile(0.7_5   )),
              ('95%', lambda lowerCAmelCase   : x.quantile(0.9_5   )),
              ('max', lambda lowerCAmelCase   : x.max()),
              ('count', lambda lowerCAmelCase   : x.count()),
              ('stdev', lambda lowerCAmelCase   : x.std()),
              ('mode', lambda lowerCAmelCase   : x.mode()[0]),
              ('median', lambda lowerCAmelCase   : x.median()),
              ('# > 0', lambda lowerCAmelCase   : (x > 0).sum()),
          ]   )
      .T.reset_index()
      .rename(index=lowerCAmelCase						,	columns={'level_0': 'Features', 'level_1': 'Type'}   )
  )  # rename columns
  # calculate the size of cluster(count of clientID's)
  SCREAMING_SNAKE_CASE_							=       report[
      (report['Features'] == 'dummy') & (report['Type'] == 'count')
  ].copy()  # avoid SettingWithCopyWarning
  SCREAMING_SNAKE_CASE_							=       (
      'ClusterSize'  # rename created cluster df to match report column names
  )
  SCREAMING_SNAKE_CASE_							=       '# of Customers'
  SCREAMING_SNAKE_CASE_							=       pd.DataFrame(
      clustersize.iloc[:, 2:].values
      / clustersize.iloc[:, 2:].values.sum()   )
  SCREAMING_SNAKE_CASE_							=       '% of Customers'  # rename created cluster df to match report column names
  SCREAMING_SNAKE_CASE_							=       'ClusterProportion'
  SCREAMING_SNAKE_CASE_							=       clusterproportion.columns.tolist()
  SCREAMING_SNAKE_CASE_							=       cols[-2:] + cols[:-2]
  SCREAMING_SNAKE_CASE_							=       clusterproportion[cols]  # rearrange columns to match report
  SCREAMING_SNAKE_CASE_							=       report.columns
  SCREAMING_SNAKE_CASE_							=       pd.DataFrame(
      abs(
          report[report['Type'] == 'count'].iloc[:, 2:].values
          - clustersize.iloc[:, 2:].values   )   )  # generating df with count of nan values
  SCREAMING_SNAKE_CASE_							=       0
  SCREAMING_SNAKE_CASE_							=       '# of nan'
  SCREAMING_SNAKE_CASE_							=       report[
      report['Type'] == 'count'
  ].Features.tolist()  # filling values in order to match report
  SCREAMING_SNAKE_CASE_							=       a.columns.tolist()
  SCREAMING_SNAKE_CASE_							=       cols[-2:] + cols[:-2]
  SCREAMING_SNAKE_CASE_							=       a[cols]  # rearrange columns to match report
  SCREAMING_SNAKE_CASE_							=       report.columns  # rename columns to match report
  SCREAMING_SNAKE_CASE_							=       report.drop(
      report[report.Type == 'count'].index   )  # drop count values except cluster size
  SCREAMING_SNAKE_CASE_							=       pd.concat(
      [report, a, clustersize, clusterproportion]						,	axis=0   )  # concat report with clustert size and nan values
  SCREAMING_SNAKE_CASE_							=       report['Features'].isin(lowerCAmelCase   )
  SCREAMING_SNAKE_CASE_							=       report.columns.tolist()
  SCREAMING_SNAKE_CASE_							=       cols[0:2] + cols[-1:] + cols[2:-1]
  SCREAMING_SNAKE_CASE_							=       report[cols]
  SCREAMING_SNAKE_CASE_							=       {
      'ClusterSize': 9,
      'ClusterProportion': 8,
      'mean_with_zeros': 7,
      'mean_with_na': 6,
      'max': 5,
      '50%': 4,
      'min': 3,
      '25%': 2,
      '75%': 1,
      '# of nan': 0,
      '# > 0': -1,
      'sum_with_na': -2,
  }
  SCREAMING_SNAKE_CASE_							=       (
      report.assign(
          Sortera=lambda lowerCAmelCase   : x.Type.map(lowerCAmelCase   )						,	Sortera=lambda lowerCAmelCase   : list(reversed(range(len(lowerCAmelCase   )   )   )   )						,	)
      .sort_values(['Sorter1', 'Mark', 'Sorter2']						,	ascending=lowerCAmelCase   )
      .drop(['Sorter1', 'Sorter2']						,	axis=1   )
  )
  SCREAMING_SNAKE_CASE_							=       ''
  SCREAMING_SNAKE_CASE_							=       report.reset_index()
  SCREAMING_SNAKE_CASE_							=       report.drop(columns=['index']   )
  return report


if __name__ == "__main__":
      import doctest

      doctest.testmod()





from __future__ import annotations


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase   )->  Union[str, Any]:
		SCREAMING_SNAKE_CASE_							=       0
		SCREAMING_SNAKE_CASE_							=       len(lowerCAmelCase   ) - 1
		while left <= right:
				SCREAMING_SNAKE_CASE_							=       (left + right) // 2
				if left == right:
						if sorted_list[middle] < item:
								SCREAMING_SNAKE_CASE_							=       middle + 1
						break
				elif sorted_list[middle] < item:
						SCREAMING_SNAKE_CASE_							=       middle + 1
				else:
						SCREAMING_SNAKE_CASE_							=       middle - 1
		sorted_list.insert(lowerCAmelCase						,	lowerCAmelCase   )
		return sorted_list


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase   )->  Any:
		SCREAMING_SNAKE_CASE_							=       []
		while left and right:
				if left[0][0] < right[0][0]:
						result.append(left.pop(0   )   )
				else:
						result.append(right.pop(0   )   )
		return result + left + right


def 				_a       (				lowerCAmelCase   )->  List[str]:
		SCREAMING_SNAKE_CASE_							=       len(lowerCAmelCase   )
		if length <= 1:
				return list_ad
		SCREAMING_SNAKE_CASE_							=       length // 2
		return merge(sortlist_ad(list_ad[:middle]   )						,	sortlist_ad(list_ad[middle:]   )   )


def 				_a       (				lowerCAmelCase   )->  list[int]:

		if len(lowerCAmelCase   ) <= 1:
				return collection
		SCREAMING_SNAKE_CASE_							=       []
		SCREAMING_SNAKE_CASE_							=       False
		for i in range(0						,	len(lowerCAmelCase   )						,	2   ):
				if i == len(lowerCAmelCase   ) - 1:
						SCREAMING_SNAKE_CASE_							=       True
				else:
						if collection[i] < collection[i + 1]:
								two_paired_list.append([collection[i], collection[i + 1]]   )
						else:
								two_paired_list.append([collection[i + 1], collection[i]]   )
		SCREAMING_SNAKE_CASE_							=       sortlist_ad(lowerCAmelCase   )
		SCREAMING_SNAKE_CASE_							=       [i[0] for i in sorted_list_ad]
		result.append(sorted_list_ad[-1][1]   )
		if has_last_odd_item:
				SCREAMING_SNAKE_CASE_							=       collection[-1]
				SCREAMING_SNAKE_CASE_							=       binary_search_insertion(lowerCAmelCase						,	lowerCAmelCase   )
		SCREAMING_SNAKE_CASE_							=       False
		for i in range(len(lowerCAmelCase   ) - 1   ):
				if result[i] == collection[-1] and has_last_odd_item:
						SCREAMING_SNAKE_CASE_							=       True
				SCREAMING_SNAKE_CASE_							=       sorted_list_ad[i][1]
				# If last_odd_item is inserted before the item's index,
				# you should forward index one more.
				if is_last_odd_item_inserted_before_this_index:
						SCREAMING_SNAKE_CASE_							=       result[: i + 2] + binary_search_insertion(result[i + 2 :]						,	lowerCAmelCase   )
				else:
						SCREAMING_SNAKE_CASE_							=       result[: i + 1] + binary_search_insertion(result[i + 1 :]						,	lowerCAmelCase   )

		return result


if __name__ == "__main__":
						SCREAMING_SNAKE_CASE:    List[str]											=   input('''Enter numbers separated by a comma:\n''').strip()
						SCREAMING_SNAKE_CASE:    Any											=   [int(item) for item in user_input.split(''',''')]
						print(merge_insertion_sort(unsorted))