Распределение слов по ячейкам таблицы

#javascript

Есть многомерный массив.

var array = [
    [
        'один',
        'два',
        'три',
        'четыре'

        // всего 16 букв
    ]
];


Список слов из array[0] должен быть размещен в таблицу, каждая буква - это отдельная
ячейка таблицы. Расположение слов в таблице - не имеет значения. Главная задача - оставить
их читаемыми по одной из сторон.

|о|д|и|н|     |ч|е|т|ы|
|ч|е|р|т|     |т|д|о|р|
|е|т|ы|р|     |р|в|д|е|
|д|в|а|и| или |и|а|и|н|


Мне кажется что вставить их без разбора на буквы - нереально. Вся проблема в том,
что некоторые слова могут быть "закручены" (не знаю как правильно сказать). Пример:

| | | | |     |ч|е|т|ы|
|ч|е|р| |     | | | |р|
|е|т|ы| |     | | | |е|
| | | | | или | | | | |


Разбор слов на буквы:

for(var value = 0; value < array[0].length; value++) { 
    for (var index = 0; index < array[0][value].length; index++) { 
        // console.log(array[0][value][index]);
    } 
}


Важные нюансы:


Общее количество букв может быть больше чем 16.
Ячеек по горизонтали может быть больше чем 4. По задумки их количество указывается
опционально var cells = 4;.
Ячеек по вертикали может быть ровно столько - сколько требуется для
размещения всех слов.
Пустых ячеек быть не должно. 


Пример:

cells = 4     cells = 4
| | | | |     | | | | |
| | | | |     | | | | |
| | | | |     | | | | |
| | | | | или | | | | |
16 букв       | | | | |
              20 букв


Над этой задачей я сижу 3й день, с 10:00 до 23:00. Очень сложный для меня алгоритм.
Буду рад любой помощи, любым советам относительно реализации.
    

Ответы

Ответ 1

Вопрос не достаточно конкретизирован. Предположу, что автор имеет ввиду следующее:

Пусть задан набор слов из N:



Пусть задано число M (== 16). Необходимо найти такие номера слов, что их суммарная
длина будет равна M. 

Решение 1

Для начала, заметим, что слова, как объекты нас не интересуют. Нам интересны лишь
их длины. Длины их обозначим через l_i. Т.е. теперь у нас есть последовательность длин
слов (их даже следует назвать множеством):



Математически строго поставим задачу (к решению имеет косвенное отношение).

В таком случае, нам нужно понять, существует ли решение хотя бы одного уравнения
A_k над нашим множеством X:



Т.е. существует ли решение уравнения 



или 



и т.д.

x_i может принимать значения из множества X ограниченное число раз.

Продолжение решения

Нам нужно найти комбинацию l_i, которые в сумме дадут M.

Отсортируем последовательность 



по убыванию и выбросим все те, для которых:

,

так как они не смогут участвовать в финальной сумме. После сортировки имеем:

,

где 

.

Теперь нам нужно перебрать все варианты решения (т.к. M=16, т.е. небольшое, то мы
в полне уложимся в перебор). Для перебора будем использовать DFS. 

Как мы это будем делать


Возьмём s_0. Проверим s_0 != M. Если равно, то решение найдено.
Попробуем подобрать для него такое число s_i, что s_0 + s_i <= M. Все варианты i
для которых s_0 + s_i > M рассматривать не будет. В силу того, что объекты отсортированы,
нам необходимо лишь перебрать их в порядке следования.
Если s_0 + s_i = M, то решение найдено. Если нет, то продолжаем поиск. 
Т.е. выберем для s_i такое s_j (j >= i), что s_0 + s_i + s_j <= M (аналогично пункту 2).


На некотором шаге может оказаться, что s_0 + s_i + s_{i+1} >= M. В таком случае дальше
осуществлять перебор не имеет смысла. Это справедливо, поскольку всё элементы отсортированы. 

Необходимо вернуться на предыдущий шаг и найти s_k (k > j). Т.е. подобрать s_0 +
s_i + s_k <= M. Если мы перебрали все возможные варианты, но не нашли сумму такую,
что она равна M, то решения нет.

Для большего понимания, как следует организовать перебор, приведу псевдокод:

def dfs(s, sum):
    for number in get_next_number(s):
        new_sum = sum + number
        answ = False
        if new_sum == m: # Если нашли решение, то выходим из перебора
            return True
        elif new_sum < m: # Если решение не нашли, то пытаемся взять следующее число
и повторить итерацию
            answ = dfs(number, new_sum)
        if answ:
            return True
    return False # Если ни в одном случае не удалось подобрать сумму, то выходим


dfs нужно запустить от каждого из имеющихся чисел s.

Точно сложность не могу оценить, но  дам верхнюю оценку. Она точно не больше O(N^3)
по времени. Но следует понимать, что это завышенная оценка. Скорее всего, реальное
время работы будет близко к O(N^2) или даже O(N log N)

Я также предполагаю, что можно предложить более умное решение динамическим программированием,
в частности, свести эту задачу, к задаче о рюкзаке.

Другое решение

Для этого решения достаточно каждому слову поставить в соответствие метку 1 или 0,
которая будет обозначать: нужно ли брать в ответ слово или не нужно. Таким образом,
мы имеем битовую маску, состоящую из 0 и 1. Нам необходимо перебрать все возможные
комбинации (их 2^N), посчитав для каждой из них суммарную длину выбранных слов. 

Приведу пример:

один // длина 4

два_  // длина 4

пять  // длина 4

три  // длина 3

четыре  // длина 6

Пусть M = 12.

Маска будет состоять из 5 битов. Будем начинать перебор с маски 00000:

10000. Слова: один. Суммарная длина 4 != M

01000. Слова: два_. Суммарная длина 4 != M

11000. Слова: один, два_. Суммарная длина 8 != M

00100. Слова: пять. Суммарная длина 4 != M

10100. Слова: один, пять. Суммарная длина 8 != M

11100. Слова: один, два_, пять. Суммарная длина 12 == M

В ответ могут войти слова:
[один, два_, пять]

Спешу заметить, что вычислительная сложность алгоритма велика: O(2^N). Т.е. уже при
30 словах вы получите достаточно долго работающий алгоритм (минута или более).

Задание размеров сетки

Что касается сетки, то для задания её размеров можно задавать A, B -- размеры её
сторон. По этим величинам вы генерируете саму сетку. A * B = M

Псевдокод

Для расположения слов, согласно вышеописанному алгоритму, можно воспользоваться "зейкой".
Вы перебираете последовательно ячейки и кладёте туда по одной букве. Предварительно,
разумеется, следует расположить все слова друг за другом:

words = 'одиндватричетыре'
letters_count = 0
for x in range(0, A):
   if x % 2 == 0:
      line = range(0, B)
   else: 
      line = range(B, 0, -1)
   for y in line:
      matrix[y][x] = words[letters_count]
      letters_count += 1