Как выполнить сортировку в соответствии с правилами, но с повторением элементов для решения циклических ссылок?

Чтобы яснее объяснить свой вопрос, я начну с объяснения реального случая, с которым я столкнулся.

] Я создаю физическую панель со многими словами, которую можно выборочно подсвечивать, чтобы составлять предложения. Вот моя ситуация:

1. Я знаю все предложения, которые хочу отобразить
2. Я хочу найти [один из] кратчайший набор ЗАКАЗАННЫХ слов, который позволяет мне отображать все предложения

Пример:

 SENTENCES:
 "A dog is on the table"
 "A cat is on the table"
 SOLUTIONS:
 "A dog cat is on the table"
 "A cat dog is on the table"

Я попытался подойти к этой проблеме с помощью «позиционных правил», которые находили для каждого УНИКАЛЬНОГО слова в наборе ВСЕ слова, используемые во ВСЕХ предложениях, какие слова должны быть слева или справа от него. В приведенном выше примере набор правил для слова «on» будет следующим: «left (A, dog, cat, is) + right (the, table)».

Этот подход работал для тривиальных случаев, но моя реальная ситуация есть две дополнительные трудности, из-за которых я застрял, и обе они связаны с необходимостью повторения слов :

1. Повторения в предложении : «кошка на столе» имеет два » ". еще лучше: в чем конкретно алгоритм), который изучает и решает такого рода проблемы? Не могли бы вы опубликовать некоторая ссылка или пример кода it?

   РЕДАКТИРОВАТЬ: Уровень сложности

   Из первого круга ответов кажется, что фактический уровень сложности (то есть, насколько предложения отличаются друг от друга) является важным фактором. Итак, вот некоторая информация по этому поводу:

   1. У меня есть около 1500 предложений, которые я хочу представить.
   2. Все предложения по сути являются модификациями ограниченного пула из ~ 10 предложений, в котором изменяются только несколько слов. Основываясь на предыдущем примере, это похоже на то, что все мои предложения будут говорить либо о «положении чьего-то домашнего животного относительно предмета мебели», либо о «физическом описании чьей-то мебели».
   3. Количество уникальных слов, используемых для создания всего количество предложений <100.
   4. Предложения состоят максимум из 8 слов.

   Для этого проекта я использую python, но любой язык достаточно читабелен (например: НЕ обфусцированный perl!) Будет хорошо.

   Заранее спасибо за ваше время!