2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Транспозиции и перестановки
Сообщение25.09.2016, 00:55 
Можно выстроить все перестановки из $n$ элементов в линию одну за другой так, что каждая перестановка будет получаться из предыдущей применением одной транспозиции. Но можно ли, соблюдая данное условие, расположить все перестановки в кольцо? Я пробовал что-то конструировать на основе решения предыдущей задачи, но у меня не получилось.
Когда я услышал эту задачу, у меня возникло еще два вопроса:
можно ли выстроить все перестановки в линию (или в кольцо), так, чтобы каждая перестановка получалась из предыдущей транспозицией соседних элементов?

 
 
 
 Re: Транспозиции и перестановки
Сообщение25.09.2016, 09:55 
Алгоритм генерирования всех перестановок, при котором каждая последующая получается из предыдущей перестановкой соседних элементов, описан, например, в книжке В.Липского "Комбинаторика для программистов".

 
 
 
 Re: Транспозиции и перестановки
Сообщение25.09.2016, 10:10 
Аватара пользователя
Да, это рассматривается, например, в "Искусстве программирования" Кнута, том 4А (или том 4 выпуск 2), параграф 7.2.1.2.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group