ВУЗ:
Составители:
Рубрика:
end;
end.
Алгоритм начинает работу с распечатки
Π
=(1,2,…,n) и заканчи-
вает ее при i=0, что происходит в случае, когда
π
1
>
π
2
>…>
π
n
, т.е.
когда получена последняя в лексикографическом порядке переста-
новка.
Сочетания
Пусть основным множеством является множество натуральных
чисел (1,2,…,n). Необходимо сгенерировать все сочетания мощно-
сти k. Рассмотрим генерацию в лексикографическом порядке. На-
пример, для
3
5
543
10
123
C
⋅⋅
==
⋅⋅
сочетаний из пяти предметов по три
получается следующий лексикографический порядок 123, 124,
125, 134, 135, 145, 234, 235, 245, 345.
Алгоритм лексикографической генерации сочетаний может
быть следующим.
Начиная с сочетания (1,2,…,k), следующее сочетание находится
просмотром текущего сочетания справа налево с тем, чтобы опре-
делить место самого правого элемента, который еще не достиг
своего максимального значения. Этот элемент увеличивается на
единицу, а всем элементам справа от него присваиваются новые
наименьшие возможные значения. Например, если n=6 и мы полу-
чили сочетание (1236) , то следующим будет сочетание (1245).
Следующий алгоритм реализует эту процедуру:
Листинг 6.2
Алгоритм генерации сочетаний.
C
0
←
-1;
for i=1 to k do C
i
←
I;
j
←
1;
while j
≠
0 do
begin
вывести (C
1
,C
2
,…,C
k
);
j
←
k;
while C
j
=n-k+j do j
←
j-1;
C
j
←
C
j
+1;
for i=j+1 to k do C
i
=C
i-1
+1;
end.
23
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
