Учитывая словарь, найдите все возможные буквы по заказу

Я был недавно спросил следующий вопрос собеседования:

У вас есть страница словаря, написанная на инопланетяне. Предположить, что язык похож на английский и читается / написано слева к верно. Кроме того, слова расположены в лексикографическом порядке. За Пример страницы может быть: ADG, ADH, BCD, BCF, FM, FN
Вы должны дать все лексикографические заказы на характер набор подарок на странице.

Мой подход выглядит следующим образом: И имеет более высокий приоритет, чем B и G имеет более высокий приоритет, чем H. Поэтому у нас есть информация о заказе для некоторых персонажей:

A->B, B->F, G->H, D->F, M->N

Возможные заказы могут быть ABDFGNHMC, ACBDFGNHMC, ... Мой подход должен был использовать массив в качестве держателя позиции и генерировать все перестановки для идентификации всех действительных заказов. Сложность времени в худшем случае это n! где n это размер набора символов. Можем ли мы сделать лучше, чем подход грубой силы.

заранее спасибо.