В контесте, где большинство задач решаются жадностью, нашел такую: "Постройте все сочетания из n элементов по k в таком порядке, чтобы два соседних сочетания отличались друг от друга не более чем одним элементом. Если существует несколько решений, выведите любое"
n и k от 1 до 15 TL 2 секунды ML 64 мб
Подразумеваются перестановка сочетаний, полученных в лексикографическом порядке, т.е. сочетание 2 1 система не засчитывает, в отличие от 1 2
Я не могу придумать параметр для сортировки, потому что количество различных элементов — относительная величина, и его не получается выражать через количество различных элементов с заданным сочетанием
Дополнительное условие для ветки рекурсии при генерации сочетаний, которое не нарушило бы их число/упорядоченность тоже не очевидно.
Как ее решать?
Насколько я помню, это умеет делать код Грея. Вроде бы достаточно его сгенерировать, а потом взять только маски, состоящие из нужного числи бит.
Да, на какой-то давней USACO была задача "The Rock Game", где нужно было вывести все маски из нужного количества бит, причем в таком порядке, чтобы любые две соседние различались не более, чем на один бит. По сути, почти тоже самое, чего от нас хотят в задаче, указаной RedLord. Код Грея; Решение. Самое интересное, что когда читал про код Грея на e-maxx, думал, что он мне никогда не пригодится. Однако:)
Спасибо!)
Если интересует не совсем наивный алгоритм(как предложили выше), а что-то более оптимальное и с доказательством, то рекомендую почитать со страницы 29 этот .doc файл.
О том же самом можно прочитать в [Окулов С.М. Дискретная математика]. В качестве исходной точки можно рассматривать также [Скиена С. Алгоритмы. Гл. 14.5].
Спасибо, почитаю!