Оценка распределения слов в сетке

Question

Я создаю поиск слова и пытаюсь вычислить качество сгенерированных головоломок, проверив, что набор слов "распределен равномерно" по всей сетке. Например, размещение каждого слова последовательно, заполнение их по строкам не особенно интересно, потому что будут кластеры, и пользователь быстро заметит шаблон.

Как я могу измерить, насколько «равномерно» распределены слова?

Что я хотел бы сделать, так это написать программу, которая использует поиск слов в качестве входных данных и выводит оценку, которая оценивает «качество» головоломки. Мне интересно, если кто-нибудь видел подобную проблему и мог бы направить меня к некоторым ресурсам. Возможно, есть какая-то концепция в статистике, которая может помочь? Спасибо.

Answer 1

Основная проблема - это распределение линий в квадрате или прямоугольнике. Вы можете сделать это геометрически или используя целочисленные массивы. Я попробую целочисленные массивы здесь.

Пусть M - матрица вашей головоломки,

A B C D
E F G H
I J K L
M N O P

Пусть слово «EFGH» будет существующим словом, а также «CGKO». Затем создайте матрицу, которая будет содержать количество членства в восьми словах в каждой ячейке:

0 0 1 0
1 1 2 1
0 0 1 0
0 0 1 0

Применение правила: текущее значение ячейки равно сумме всех соседей (четырехстороннее) и умножается на исходное значение ячейки, если исходное значение равно 2 или выше.

0 0 1 0      1 2 2 2
1 1 2 1  -\  1 3 8 2
0 0 1 0  -/  1 2 3 2
0 0 1 0      0 1 1 1

И суммируем все значения в строках и столбцах матрицы:

1 2 2 2 =  7
1 3 8 2 = 14
1 2 3 2 =  8
0 1 1 1 =  3
| | | |
3 7 | 6
    14

Затем вычислите среднее значение обоих наборов результатов:

(7 + 14 + 8 + 3) / 4 = 32 / 4 = 8
(3 + 7 + 14 + 6) / 4 = 30 / 4 = 7.5

И вычислите среднюю разницу для среднего значения каждого набора результатов:

3  <-> 7.5 = 4.5       7  <-> 8 = 1
7  <-> 7.5 = 0.5       14 <-> 8 = 6
14 <-> 7.5 = 6.5       8  <-> 8 = 0
6  <-> 7.5 = 1.5       3  <-> 8 = 5
             ___avg               ___avg
             3.25                 3

И умножьте их вместе:

3 * 3.25 = 9.75

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

Вот пример плохого распределения:

1 0 0 0      1 1 0 0      2
1 0 0 0  -\  2 1 0 0  -\  3         -\  C avg 2.5  -\  C avg-2-avg 0.5
1 0 0 0  -/  2 1 0 0  -/  3         -/  R avg 2.5  -/  R avg-2-avg 2.5
1 0 0 0      1 1 0 0      2                                       _____*
                           6 4 0 0                                 1.25 < score

Редактировать: рассчит. исправлены ошибки.