Алгоритм Jumble - Jumble algorithm

Эта статья об алгоритмах решения и создания словесной игры. Для использования в других целях см. Ералаш (значения).

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

Компьютеризированное решение

Были разработаны алгоритмы для решения Jumbles с использованием словаря. Общие алгоритмы работают путем печати всех слов, которые могут быть составлены из набора букв. В решатель затем выбирает правильное слово.

Первый алгоритм:

  1. Начинать
  2. Ввод: J, все перемешанные буквы, образующие неизвестное слово (слова) W.
  3. Сортируйте буквы J в алфавитном порядке, сохраняя дубликаты.
  4. Найдите отсортированные буквы в хэш-таблице, инициализированной словарем, которая сопоставляет отсортированный набор букв с нешифрованными словами.
  5. Выведите набор слов, который равен W
  6. Конец

Второй алгоритм:

  1. Начинать
  2. Ввод: J, все перемешанные буквы, образующие неизвестное слово (слова) W.
  3. Составьте список слов Y со всеми перестановки из J
  4. Для каждого слова в Y проверьте, существует ли слово в словаре
  5. Если совпадение найдено, соберите его в список слов W
  6. Выведите слова в W
  7. Конец

Алгоритм нахождения перестановки из J:

  1. Начинать
  2. Инициализируйте строку с первым символом J, обозначенным J (1)
  3. Добавьте второй символ J, обозначенный J (2), по обе стороны от J (1), чтобы получить две строки

J (1)J (2)


J (2)J (1)

  1. Добавьте третий символ J, обозначенный J (3), с каждой стороны и между двумя вышеуказанными строками, чтобы получить 6 строк.

Дж (1) Дж (2)J (3)


J (1)J (3)J (2)


J (3)Дж (1) Дж (2)


Дж (2) Дж (1)J (3)


J (2)J (3)J (1)


J (3)Дж (2) Дж (1)

  1. Таким же образом добавьте J (4) к каждой из вышеперечисленных строк с обеих сторон и между двумя символами, чтобы получить 24 строки.
  2. Продолжайте это, пока все персонажи не будут завершены

Хотя алгоритм выглядит сложным, его легко запрограммировать.

Дуглас Хофштадтер разработал программу под названием Джамбо который пытается решать проблемы Jumble, как это сделал бы человеческий разум. Программа не полагается на словарь и не пытается найти настоящие английские слова, а скорее слова, которые могут быть английскими, используя базу данных вероятностей для различных комбинаций букв Буквы комбинируются недетерминированно, следуя стратегии, вдохновленной химическими реакциями и свободными ассоциациями.