Изменения

Перейти к: навигация, поиск
Описание алгоритма
* Если же ребра нет, то найдем такую вершину <tex>\mathrm{v}_j</tex> (то, что она всегда существует, будет показано ниже), что <tex> \mathrm{v}_j \in{\mathbb{V}} \setminus \{ \mathrm{v}_i, \mathrm{v}_{i+1} \} </tex>, и существуют ребра <tex> \mathrm{v}_i \mathrm{v}_j</tex> и <tex> \mathrm{v}_{i+1} \mathrm{v}_{j+1} </tex> (Если <tex> j = n</tex> , то за <tex>\mathrm{v}_{j+1}</tex> считаем <tex>\mathrm{v}_{1}</tex>).
** Если <tex>i < j </tex> то перевернем часть перестановки от <tex> i+1 </tex> до <tex> j </tex> (включительно).
** Если <tex> i > j </tex> обменяем в перестановке элементы на позициях <tex> (i + 1 + k)\ \operatorname{mod}\ n </tex> и <tex> (j - k +n)\ \operatorname{mod}\ n </tex>, где <tex>k = \overline{0, (j + n - i)\ \operatorname{div}\ 2}</tex>, то есть считаем <tex>\mathrm{v}_{i}...\mathrm{v}_{j}</tex> равным <tex>\mathrm{v}_{i}...\mathrm{v}_{n}\mathrm{v}_{1}...\mathrm{v}_{j}</tex>. Например, если <tex>n = 10, i = 8, j = 1</tex>, то <tex>\mathrm{v}_9 </tex> и <tex>\mathrm{v}_1</tex> поменяются местами, а <tex>\mathrm{v}_{10}</tex> останется на месте.
== Псевдокод ==
71
правка

Навигация