Как найти наибольший общий делитель с округлением?

Пользователь настукивает короткий ритмический рисунок из нот всего двух длительностей: x или 2x. Примерно как азбука Морзе, только музыкально, в темпе. В итоге получен массив длительностей нот в миллисекундах, например:
[145,160,112,170,281,292,258,305,257]
график
5d789a292ed10066227417.png


Как эти длительности классифицировать в ноты кратных длительностей? Как заменить на "1" для коротких x и на "2" для длинных 2x, чтобы для примера выше получилось
[1,1,1,1,2,2,2,2,2]

Наивный способ не работает

const a = [145,160,112,170,281,292,258,305,257];
const min = Math.min(...a); // 112
a.map(n => Math.round(n / min)) // [ 1, 1, 1, 2, 3, 3, 2, 3, 2 ]


Этот вопрос только про бинарную классификацию x || 2x.

Далеко потом, уже другим способом, может быть будет интересно суметь разбирать «мелодию» без самых коротких нот, состоящуя только из кратных 2x и 3x. Или ещё сложнее – полиритмия с рациональными дробями: 4/4 затем в этом же темпе 6/4 или 5/4. Но это не сейчас.

Upd. реализация решения Владимир Олохтонов на JS
spoiler
const AB = data => {
  
  const A = [Math.min(...data)];
  const B = [Math.max(...data)];
  
  const mean = arr => arr.reduce((a,b) => a + b, 0) / arr.length;

  data.forEach(n => {
    if (Math.abs(mean(A) - n) <= Math.abs(mean(B) - n))
      A.push(n);
    else B.push(n);
  });
  
  return [A.slice(1), B.slice(1)];
}
 
AB([145,160,112,170,281,292,258,305,257])

/*
[[145,160,112,170],[281,292,258,305,257]]
*/
  • Вопрос задан
  • 83 просмотра
Решения вопроса 2
adugin
@adugin
Можно воспользоваться одним из алгоритмов кластеризации в scikit-learn, например KMeans:
>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> notes = [145, 160, 112, 170, 281, 292, 258, 305, 257]
>>> notes = np.array(notes).reshape(-1, 1)
>>> KMeans(n_clusters=2).fit_predict(notes)
array([0, 0, 0, 0, 1, 1, 1, 1, 1], dtype=int32)

Но порядок присвоения номеров кластерам не гарантируется. Кластеризация просто позволяет выборку на N частей, присвоим каждому кластер произвольный порядковый номер. Может быть и так:
>>> KMeans(n_clusters=2).fit_predict(notes)
array([1, 1, 1, 1, 0, 0, 0, 0, 0], dtype=int32)
Ответ написан
sgjurano
@sgjurano
Разработчик
Ваши данные можно представить как набор точек на числовой прямой, сгруппированных где-то около среднего по интервалу, нужно решить задачу классификации.

Сложность в том, что вы не знаете заранее абсолютные значения величин. Ровно эту задачу решает кластерный анализ и простейший его метод К-средних.

Вы так же можете применить эвристику, поскольку в исходной формулировке групп всего две: отсортируйте массив длительностей и примите за исходные положения центроидов его крайние элементы, затем поочередно добавляйте элементы в ближайшую группу, пересчитывая среднее после каждой вставки.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Beshere
@Beshere
Инженер-программист
Мне кажется, тут нужен кластер-анализ.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы