У Жени накопился большой список игр разных жанров. Он решил разбить их на две непустых папки так, чтобы игры из первой части списка попали в одну папку, а из второй — в другую.
Женя решил оценить энтропию получившегося разбиения, однако на его калькуляторе отсутствует функция логарифма, поэтому он решил оценивать качество распределения жанров игр по папкам при помощи следующей оценки:
где N1 и N2 — число игр в первой и второй папке соответственно, K — число возможных жанров, а pf,i — вероятность встретить игру жанра i в f-й папке. Эта вероятность оценивается как pf,i = countf[i] / Nf, где countf[i] — число игр жанра i в f-й папке.
Помогите Жене определить качество распределения жанров игр по папкам для всех возможных непустых разбиений списка игр.
Задача сводится к тому, чтобы для каждого возможного непустого разбиения списка игр на две папки вычислить значение качества разбиения по заданной формуле. Рассмотрим пошагово, как решать эту задачу:
**Дано:**
- Общее число игр — \( N \).
- В списке игр есть \( K \) жанров.
- Есть последовательность игр, каждая с жанром \( i \).
**Что нужно сделать:**
- Перебрать все возможные разбиения списка игр на две непустых папки.
- Для каждого разбиения:
- Посчитать количество игр каждого жанра (например, \( count_1[i] \) для первой папки — жанр \( i \), \( count_2[i] \) для второй папки).
- Вычислить вероятности:
\[
p_{f,i} = \frac{count_f[i]}{N_f}
\]
где \( N_f \) — количество игр в папке \( f \).
- Вычислить значение качества разбиения по формуле:
\[
Q = -N_1 \sum_{i=1}^K p_{1,i} \log p_{1,i} - N_2 \sum_{i=1}^K p_{2,i} \log p_{2,i}
\]
Важно учитывать, что при \( p_{f,i} = 0 \), вклад в сумму равен 0 (так как \( 0 \log 0 \) считается равным 0).
---
### Шаги решения
1. **Подготовка данных:**
- Задача предполагает, что у вас есть список игр с жанрами. Например: \([g_1, g_2, ..., g_N]\), где каждый элемент — жанр.
2. **Перебор разбиений:**
- Перебираем все возможные разбиения в виде:
\[
i = 1, 2, ..., N-1
\]
— тут \( i \) — индекс, после которого разбивается список:
- Первая папка — игры с индексами от 1 до \( i \).
- Вторая папка — игры с индексами от \( i+1 \) до \( N \).
3. **Подсчет жанров в каждой части:**
- Для каждого разбиения:
- Подсчитаем количество игр каждого жанра в первой части.
- Подсчитаем количество игр каждого жанра во второй части.
4. **Вычисление вероятностей и качества разбиения:**
- Для каждой папки:
- Вычисляем \( p_{f,i} = count_f[i] / N_f \).
- Вносим вклад в сумму: \( p_{f,i} \log p_{f,i} \), если \( p_{f,i} > 0 \).
5. **Вывод результата:**
- Для каждого разбиения выводим вычисленное значение \( Q \).
---
### Пример кода (на Python)
```python
import math
def compute_quality(songs, K):
N = len(songs)
results = []
for i in range(1, N):
# Подсчет жанров в первой папке
count1 = [0] * K
for genre in songs[:i]:
count1[genre] += 1
N1 = i
# Подсчет жанров во второй папке
count2 = [0] * K
for genre in songs[i:]:
count2[genre] += 1
N2 = N - i
# Функция для подсчёта суммы p*log p
def entropy_part(counts, total):
sum_val = 0.0
for c in counts:
if c > 0:
p = c / total
sum_val += p * math.log(p)
return sum_val
# Вычисление Q для этого разбиения
Q = -N1 * entropy_part(count1, N1) - N2 * entropy_part(count2, N2)
results.append(Q)
return results
# Пример использования:
# Индексы жанров начинаются с 0
songs = [0, 1, 0, 2, 1, 0]
K = 3 # жанры: 0, 1, 2
values = compute_quality(songs, K)
for idx, val in enumerate(values, 1):
print(f"Разбиение после игры {idx}: Q = {val}")
```
---
### Итоги
- Можно перебрать все разбиения.
- Для каждого — подсчитать жанры в обеих папках.
- Построить вероятность и вычислить качество по формуле.
Это позволяет оценить, насколько равномерно распределяются жанры по папкам для всех возможных разбивок. Если есть дополнительные вопросы или требуется помощь с конкретными данными — обращайтесь!
