Сочетания

Сочетанием из n элементов по m (иногда читают просто: из n по m) называется m-элементное подмножество некоторого n-элементного множества.

Таким образом, чтобы назвать какой – либо объект сочетанием из n по m, необходимо проверить одновременное выполнение следующих условий (существенных признаков понятия «сочетание»):

1. Заданы два множества.

2. Одно из множеств является подмножеством другого.

3. Основное множество содержит n элементов.

4. Подмножество содержит m элементов.

Число сочетаний из n элементов по m обозначается через и вычисляется по формуле:

Пример: Сколькими способами можно составить букет из 3 цветов, если в вашем распоряжении 5 цветов: мак, роза, тюльпан, лилия, гвоздика?

Решение:

Основное множество: {мак, роза, тюльпан, лилия, гвоздика} => n=5

Соединение – букет из трех цветков => m=3

Проверим, важен ли порядок:

{тюльпан, лилия, гвоздика} и {лилия, тюльпан, гвоздика} – один и тот же букет => порядок неважен => это подмножество => это сочетание «из пяти по три».

(букетов) Ответ: 10 букетов

Генерирование сочетаний.

Опишем алгоритм генерирования всех k-элементных подмножеств n-элементного множества X. Можно принять X = {1,..., n}. Тогда каждому k-элементному подмножеству взаимнооднозначно со­ответствует возрастающая последовательность длины kс элементами из X:на­пример, подмножеству {3,5,1} соответствует последовательность (1,3,5). Мож­но легко указать алгоритм, с помощью которого генерируются все такие после­довательности. Для этого достаточно заме­тить, что при таком порядке, последовательностью, непосредственно следующей за последовательностью (a₁,..., а_k), является (b₁,...,b_k) = (a₁,...,a_p-i,a_p + 1 ,a_p + 2,...,a_p + k-p+1), где p=max{i:a_i<n-k+1}.

Более того, последовательностью, непосредственно следующей за (b₁,…,b_k), является

(c₁,...,c_k) = (b₁,...,b_p’-1,b_p’ +1, b_p’ +2,..., b_p’> +k-p’ + 1), где

(будем предполагать, что последовательности (a₁,...,a_k) и (b₁,...,b_k) отлича­ются от (n-k+1,...,n) — последней последовательности в нашем порядке.

Это приводит к следующему простому алгоритму.

Алгоритм. (Генерирование всех k-элементных подмножеств множе­ства {1,...,n}.)

Данные: n, к.

Результат: последовательность всех k-элементных подмножеств множества {1,...,n}.

1.begin

2. for i:=1 to k do A[i]:=i; (*первое подмножество*)

3. p:=k;

4. while p≥1 do

5. begin write (A[1],…,A[k]);

6. if A[k]=n then p:=p-1 else p:=k;

7. if p≥1 then

8. for i:=k downto p do A[i]:=A[p]+i-p+1;

9. end;

10.end.

Последовательность всех 4-элементных подмножеств множества {1,...,6}, полученная с помощью этого алгоритма, выглядит следующим образом:

Дата добавления: 2014-01-20