Сочетания

3 Сочетания

Пусть имеем 5 компонент, обозначенных латинскими буквами A, B, C, D, E соответственно.

Тогда все сочетания из этих 5 компонент по 3, выписанные в лексикографическом порядке (для букв и цифр от 1 до 5) будут таковы:

ABC 123

ABD 124

ABE 125

ACD 134

ACE 135

ADE 145

BCD 234

BCE 235

BDE 245

CDE 345

Неформально алгоритм генерации последовательности чисел в лексикографическом порядке можно записать следующим образом. Выберем наименьшие M из имеющихся N чисел и выпишем их в порядке возрастания - и выпишем их в порядке возрастания - 1 2 3 - это начальное сочетание. Очевидно, что наибольшие M чисел из имеющихся (3 4 5), выписанные в порядке возрастания, составят последнее сочетание.

Для того, что бы по текущему сочетанию получать следующее, можно поступать следующим образом:

Находим позицию в текущем сочетании, на которой не стоит последнее из возможных значений, и затем увеличиваем его на 1. А все последующие элементы сочетания получаем увеличением на 1 предыдущего элемента сочетания.

Например пусть текущее сочетание

1 3 5

Анализ начинаем с последней позиции сочетания.

5 - это последнее возможное значение, потому переходим к предыдущей позиции. 3 - это не последнее возможное значение для этой позиции (каковым является 4 в данном случае). Потому мы его увеличиваем на 1 - получаем 4. А число в следующей позиции получаем прибавлением 1 к этой 4-ке - и получаем 5. Таким образом следующее значение будет 1 4 5

Более формализовано этот алгоритм может быть записан следующим образом:

Ввод N, M (из сколька, по сколько)

Заносим в массив B числа от 1 до M

Это первое сочетание, выводим его

Пока (истина)

i=M

Пока (i>0) и (b[i]=N-m+i), i=i-1

Если i=0 то работа завершена

B[i]=B[i]+1

Для j от i+1 до M B[j]=B[j-1]+1;

Вывод B - следующей перестановки

Ниже приводится программа, которая считывает с клавиатуры значения N и M и выводит в лексикографическом порядке все сочетания из N первых латинских букв по M.

uses crt;

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b : array [1..100] of byte;

N,M,i,j,k : byte;

Procedure WriteB;

begin

for i:=1 to M do write(alphabet[b[i]]);

writeln;

end;

begin

readln(N,M);

for i:=1 to M do b[i]:=i;

WriteB;

while (true) do

begin

i:=M;

while (i>0) and (b[i]=N-m+i) do Dec(i);

if i=0 then exit;

Inc(B[i]);

for j:=i+1 to M do B[j]:=B[j-1]+1;

WriteB;

end;

end.

Напомним, что общее число сочетаний из N элементов по M может быть вычислено по формуле C (N,M) = N! / (M! * (N-M)! )

4 Размещения

Для генерации всех размещений из N элементов по M можно воспользоваться композицией алгоритмов, изложенных выше. То есть генерировать все сочетания из N по M, а затем для каждого полученного сочетания генерировать все перестановки из M элементов.

Например, при генерации всех размещений из 5 элементов по 3, в случае, если сами элементы обозначены латинскими буквами A,B,C,D,E нужно получить следующую последовательность, представленную для компактности в виде 10 строк, каждая из которых представляет все возможные сочетания из 3 букв первого элемента строки. А сами первые элементы строк как раз и представляют все возможные сочетания из 5 букв по 3.

ABC ACB BAC BCA CAB CBA

ABD ...

ABE ...

ACD ...

ACE ...

ADE ...

BCD ...

BCE ...

BDE ...

CDE CED DCE DEC ECD EDC

Общее количество pазмещений - из N элементов по M может быть

найдено по формуле:

N! / (N-M)!

Ниже приводится программа, которая вводит с клавиатуры числа N, M и генерирует все возможные размещения из N букв по M.

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

type

barray = array [1..100] of byte;

var

b : barray;

N,M,i,j,k : byte;

z : longint;

Procedure WriteB(B:barray);

begin

Inc(Z); Write (Z:3,' : ');

for i:=1 to M do write(alphabet[b[i]]);

writeln;

end;

Procedure SwapB(var B:barray;i,k:byte);

var x : byte;

begin

x:=B[i]; B[i]:=B[k]; B[k]:=x;

end;

Procedure PermuteAll(B:barray;N:byte);

var i,k,j : byte;

begin

WriteB(B);

while (true) do

begin

i:=N;

while (i>0) and (B[i]>=B[i+1]) do i:=i-1;

if i=0 then exit;

for j:=i+1 to N do

if (B[j]>B[i]) then K:=j;

SwapB(B,i,k);

for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(B,j,N+i+1-j);

WriteB(B);

end;

end;

begin

readln(N,M);

for i:=1 to M do b[i]:=i;

PermuteAll(B,M);

while (true) do

begin

i:=M;

while (i>0) and (b[i]=N-m+i) do Dec(i);

if i=0 then exit;

Inc(B[i]);

for j:=i+1 to M do B[j]:=B[j-1]+1;

PermuteAll(B,M);

end;

readln;

end.

Пояснения к программе:

1. Главная программа вводит числа N, M и генерирует по описанному выше алгоритму все сочетания из N по M. Для каждого построенного в векторе B сочетания вызывается процедура PermuteAll, которой в качестве параметров передаются текущее сочетание B и количество элементов в нем M. Процедура PermuteAll генерирует для полученного сочетания все возможные перестановки.

2. Массив B передается в процедуру PermuteAll по значению (при объявлении процедуры при параметре B нет ключевого слова VAR) и потому изменения массива B в процедуре PermuteAll не влияют на содержимое массива B в главной программе.

3. В то же время для того, что бы процедура SwapB могла обменивать значения в B и возвращать измененный массив в вызывающую ее процедуру PermuteAll, массив B добавлен в параметры процедуры SwapB с передачей по адресу - используя ключевое слово VAR.

4. Для передачи массива в качестве параметра заведен специальный тип BARRAY.

5. Для подсчета всех сгенерированных размещений используется переменная Z в процедуре WriteB.

5 Перестановки с повторениями

Перестановки с повторениями допускают повторное использование элементов. Например, пусть имеем множество, состоящее из двух символов A и двух символов B.

Тогда все перестановки с повторениями из этих символов будут таковы:

AABB ABBA BABA ABAB BAAB BBAA

В общем случае, если имеем

N1 предметов 1-го вида

N2 предметов 2-го вида

...

Nk предметов K-го вида

Общее количество перестановок может быть вычислено по формуле

N!/ (N1!*N2!*..*Nk!)

Алгоритм аналогичен генерации перестановок без повторений за исключением формирования начальной перестановки:

i=0;

Для j от 1 до k

Для m от 1 до N[j] i=i+1; B[i]=j;

Ниже приводится программа генерации перестановок с возвращениями. Количество K различных типов предметов, обозначенных латинскими буквами вводится с клавиатуры. С клавиатуры также вводятся количества NN[j] предметов каждого типа.

Сумма введенных NN[j] определяет общее количество элементов в каждой из генерируемых перестановок.

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b : array [1..100] of byte;

N,i,j,k,m : byte;

NN : array [1..100] of longint;

Procedure SwapB(i,k:byte);

var x : byte;

begin

x:=B[i]; B[i]:=B[k]; B[k]:=x;

end;

Procedure WriteB;

begin

for i:=1 to N do write(alphabet[b[i]]);

writeln;

end;

begin

readln(K);

N:=0;

for i:=1 to K do

begin read(NN[i]); N:=N+NN[i]; end;

i:=0;

for j:=1 to k do

for m:=1 to NN[j]

do begin Inc(i); B[i]:=j; end;

WriteB;

while (true) do

begin

i:=N;

while (i>0) and (B[i]>=B[i+1]) do i:=i-1;

if i=0 then exit;

for j:=i+1 to N do if (B[j]>B[i]) then K:=j;

SwapB(i,k);

for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j);

WriteB;

end;

end.

 

6 Сочетания с повторениями

Для множества символов от A до C и размера M=3 сочетания с повторениями будут следующими:

CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA

Общее количество сочетаний = (N+M-1)! / (M!*(N-1)!)

где N - количество символов

M - по сколько символов в сочетании

Основная идея генерации таких сочетаний с повторениями заключается в следующем:

Сочетания записываем в виде (N-1)-го нуля и M единиц ,где единицы заменяют символы, а нули выступают в pоли pазделителей.

Напpимеp:

ABB - 1 0 1 1 AAC - 1 1 0 0 1 C C C - 0 0 1 1 1

A B B A A C C C C

При таком подходе для решения задачи достаточно сгенерировать все перестановки из M единиц и N-1-го нуля.

Ниже приводится программа, которая решает поставленную задачу.

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b : array [1..100] of byte;

N,i,j,k,M,N1 : byte;

Procedure SwapB(i,k:byte);

var x : byte;

begin

x:=B[i]; B[i]:=B[k]; B[k]:=x;

end;

Procedure WriteB;

var i,j : byte;

begin

j:=1;

for i:=1 to N do

if b[i]=0

then Inc(j)

else write(alphabet[j]);

writeln;

end;

begin

readln(N1,M); N:=N1-1+M;

for i:=1 to n1-1 do b[i]:=0;

for i:=n1 to n1+m-1 do b[i]:=1;

WriteB;

while (true) do

begin

i:=N;

while (i>0) and (B[i]>=B[i+1]) do i:=i-1;

if i=0 then exit;

for j:=i+1 to N do

if (B[j]>B[i]) then K:=j;

SwapB(i,k);

for j:=i+1 to (i+ ((N+1-i) div 2)) do

SwapB(j,N+i+1-j);

WriteB;

end;

end.

Пояснения к программе:

1. Начальная перестановка формируется последовательно из N1-1 нулей и M единиц.

2. В программе вывода перестановки WriteB осуществлены изменения, соответствующие замыслу (нули - разделители, единицы - символы). Если текущий элемент массива B равен 0, то "становится активным" следующий символ. Если текущий символ массива B равен 1, то текущий активный символ выводится на экран.

Заключение

Все программы для большей наглядности в качестве иллюстрации оперируют с массивом символов от A до Z. Очевидно, что предлагаемые алгоритмы и программы практически не изменяются при работе с массивами элементов любого типа, требуемого по условиям задачи (например, массивами чисел, слов, геометрических фигур и т.д.)

Литература

1. Абдеев Р.Ф. Философия информационной цивилизации. - М.: Владос, 1994.

2. Адамар Ж. Исследование психологии процесса изобретения в области математики. - М.: Сов. радио, 1970.

3. Болтянский В.Г. Информатика и преподавание математики// Математика в школе. 1989. № 4.-С.86-90

4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. - М.: Радио и связь, 1982.

5. Вирт Н. Алгоритмы+Структуры данных=Программа. - М.:Мир, 1989

6. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977.

7. Громов Г.Р. Очерки информационной технологии. - М.: ИнфоАрт, 1993.

8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.

9. Ильенков Э. В. Философия и культура. - М.: Полит. лит., 1991.

10. Йодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979.

11. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980.

12. Махмутов М.И. Организация проблемного обучения в школе. - М., 1986.