генерировать все таблицы непредвиденных обстоятельств с заданными полями по гамильтоновому пути
Таблица записей на случай непредвиденных обстоятельств n[t,s] с участием t=1,...,k а также s=1,...,q. Вот,k>1, q>1 и n[t,s] неотрицательные целые числа.
Предположить, что
sum_s n[t,s] = a_t >= 0
sum_t n[t,s] = b_s >= 0
фиксированные маржи для всех доступных t а также s.
Я хочу создать все таблицы непредвиденных обстоятельств, соответствующие таким маргиналам. Более того, я хочу сгенерировать их таким образом, чтобы на каждом этапе генерации изменялись только несколько элементов таблицы. По-видимому, достаточно 4 измененных записей на шаг, как указано в:
Д. Кнут, Искусство компьютерного программирования, Том 4A: Комбинаторные алгоритмы, Часть 1 (2014), ISBN=9780201038040, в разделе 7.2.1.3, Создание всех комбинаций, упражнения 62-63.
Формально проблему можно сформулировать следующим образом. Каждую возможную таблицу сопряженности с заданными маргиналами можно отождествить с вершинами графа с парами связанных вершин тогда и только тогда, когда связанные таблицы сопряженности отличаются не более чем на 4 записи. Как упоминалось в книге, такой граф допускает гамильтонов путь. У меня вопрос: какой алгоритм может "генерировать" такой путь?