ВУЗ:
Составители:
Рубрика:
22
жет быть следующим. Начиная от перестановки (1,2,…,n), мы пе-
реходим далее от
Π
=(
π
1
,…,
π
n
) и ее последующей путем просмотра
Π
справа налево в поисках самой правой позиции, в которой
π
i
+
π
i+1
. Найдя ее, мы теперь ищем
π
j
, наименьший элемент, распо-
ложенный справа от
π
i
и больший его; затем осуществляется
транспозиция элементов
π
i
и
π
j
и отрезок
π
i+1
,…,
π
n
переворачива-
ется.
Например, для n=8 и
Π
=(2,6,5,8,7,4,3,1) мы имеем
π
i
=5,
π
j
=7,
меняя их местами, получаем (2,6,7,8,5,4,3,1). Переворачивая отре-
зок
π
i+1
,…,
π
n
получаем новую перестановку (2,6,7,1,3,4,5,8), сле-
дующую за
Π
в лексикографическом порядке.
Следующий алгоритм реализует эту процедуру (в квадратных
скобках даны комментарии):
Листинг 6.1
Алгоритм генерации перестановок в лексикогра-
фическом порядке.
for j=0 to n do
π
j
←
j;
i
←
1;
while i
≠
0 do
begin
вывести
Π
=(
π
1
,…,
π
n
);
[Найти самое правое место, где
π
i
<
π
i+1
.]
i
←
n-1;
while
π
i
>
π
i+1
do i
←
i-1;
[Найти
π
j
, наименьший элемент справа от
π
i
и больший
его]
j
←
n;
while
π
i
>
π
j
do j
←
j-1;
[Поменять местами
π
i
и
π
j
и затем перевернуть
π
i+1,…
π
n
]
π
i
⇔
π
;
j
r
←
n;
s
←
i+1;
while r>s do
begin
π
r
⇔π
s
;
r
←
r-1;
s
←
s+1;
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
