Комбинаторика. Формирование комбинаторных групп из N по К (К - от 1 до N)

Комбинаторика. Орын ауыстыру (перестановка), орналастыру (размещение)

Орын ауыстыру

Мысал 1. 10 адам кезекте қанша әдіспен тұруы мүмкін?

Бұл сеспті талқылай отырып, 10 адамды кезектің 10 орнында орналастыру қажет екені түсінікті болып отыр, яғни 10 элементтен 10 бойынша орналастыру қажет - . Ол мынаған тең:

= 10 9 8 ... 3 2 1 = 10!

n элементтен n бойынша орналастыру n элементтен алмастыру деп аталады. Осылайша, n элементтен екі түрлі алмастыру бір-бірінен элементтер санымен емес, элементтердің орналасу ретімен ерекшеленеді. Анықтама. M = {a₁, a₂, ..., a_n} ақырғы жиыны бар болсын. М жиынының n элементінен тұратын әрбір реттелген жиын осы жиынның алмастыруы деп аталады

Анықтамаға сәйкес n элементтен алуан түрлі алмастырулар саны төмендегіге тең:

Ұмытпаңыздар, 0! = 1.

Берілген есепті шешу үшін санның факториалын есептейтін процедурасы бар программаны құру қжет.

Program mіsal6;

uses WіnCrt;

var

n, f : longіnt;

{----------------------------------------------------------------------------------------}

Procedure Factorіal(n : іnteger; var f : longіnt);

var

і : іnteger;

begіn

f := 1;

іf n = 0 then f := 1

else for і := 1 to n do f := f*і

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('Жиынның элементтер санын енгізіңіз '); readln(n);

Factorіal(n, f);

wrіteln('Он адам кезекте ', f, ' әдіспен тұруы мүмкін')

end.

Мысал 7. 2, 3, 4, 5, 9 цифрларынан қанша жұп бес таңбалы сан құруға

болады?

Шешімнің математикалық алгоритмі

Жұп сандар жұп цифрмен аяқталады. Берілген мысалда жұп сандар екеу.

Айталық, жұп санның бірі барлық жағдайда ең соңғы орында орналассын, онда барлық алынатын сандар жұп болады. Мұндай сандар нешеу болады? Оның саны қалған 4 цифрдан алынатын алмастырулар санына, яғни 4!-ға тең. Бірақ берілген сандардың ішінде тағы бір жұп сан бар. Айталық, енді осы екінші жұп сан да ең соңғы орында орналассын. Онда тағы да жұп сандар шығады және оның саны 4!-ға тең.

Нәтижеде бес таңбалы жұп сандар саны 2*4! болады.

Программаны құру қиынға соқпайды. Сондықтан да оны өз бетінше құрыңыздар.

Тапсырма 3

0, 1, 2, 3, 5 цифрларымен 5-ке бөлінетін қанша бес таңбалы сан құруға болады?

Орналастыру

Алдымен математикадағы, оның ішінде жиындар теориясындағы кейбір ұғымдарды еске түсірейік.

Біріншіден, жиын дегеніміз не? Жиын ұғымы математикада негіз қалаушы және анықталмаған болып табылады.

Жиын дегеніміз қандай да бір ортақ белгісі бойынша біріккен объектілер жиынтығы

Осылайша, сыныптағы орындықтар мен үстелдер жиыны жөнінде, натурал сандар жиыны, бүтін, рационал және нақты сандар жиыны туралы айтуға болады.

Жиынға кіретін объектілерді элементтер деп атаймыз.

5 саны натурал сандар жиынының элементі болады. Үстел сыныптағы үстелдер жиынының элементі болады. Әдетте жиындар A, B, C, D, ..., X, Y, Z латынның бас әріптерімен белгіленеді, ал олардың элементтері a, b, c, d, ..., x, y, z кіші әріптермен белгіленеді.

а А жиынының элементі дегенді а А жиынына тиісті дейді.

Әдетте жиын элементтері фигуралы жақша ішінде жазылады:

Бізге элементтері көрсетілген А жиыны және B = {a₁, a₂, a₃, a₄} жиыны берілсін.

Байқағанымыздай, В жиынының әрбір элементі А жиынының да элементі болады. Бұл жағдайда В жиынын А жиынының ішкі жиыны деп айтады.

Анықтама..Егер В элементінің әрбір элементі А жиынының да элементі болса, онда В А-ның ішкі жиыны деп аталады.

Көп жағдайда бізге жиын элементтерін ғана емес, сонымен қатар олардың жиындағы орналасу ретін де білу қажет болады.

Егер жиындағы элементтердің орналасу реті ескерілсе, онда орналасу реті әр түрлі бірдей элементтері бар жиындар біз үшін әр түрлі жиындар болып саналады.

Мысалы: Z = {z₁, z₂, z₃, z₄ } и B = {z₂, z₁, z₃, z₄} әр түрлі жиындар болып саналады, өйткені оларда жиындардың орналасу реті әр түрлі.

Элементтердің орналасу реті берілген жиын реттелген деп аталады

Қарапайым мысалдар қарастырайық.

1-мысал. Сыныпта 12 оқу пәні бар. Бір күнде 5 әр түрлі сабақ өтіледі. Сабақ кестесі қанша түрлі әдіспен құрылуы мүмкін.

Оқу пәндерін 1-ден 12-ге дейінгі цифрлармен белгілейік:

1, 2, 3, 4, 5, ..., 10, 11, 12.

Есептің шарты бойынша осы 12 санның ішінен 5 саннан таңдау қажет. Осы бес саннан тұратын таңдау сандармен ғана емес, олардың орналасу ретімен де ерекшеленуі тиіс, мысалы, терімнің бірі келесідей болуы мүмкін: {1, 2, 3, 4, 5}; осы сандарды алмастыруда шығатын {2, 1, 3, 4, 5} терімі де есептің шартын қанағаттандырады.

Шынында да, бірінші терім келесі пәндерден тұратын болсын: {алгебра, физика, химия, тарих, әдебиет}; онда ең болмағанда екі пәнді алмастыру барысында алынған терім сабақтың жаңа кестесін береді: {физика, алгебра, химия, тарих, әдебиет}.

Осылайша, 5 саннан тұратын терім сандармен ғана емес, олардың орналасу ретімен де ерекшеленуі мүмкін.

Мұндай ішкі жиындар комбинаторикада орналастырулар деп аталады.

Анықтама. k бойынша n элементтен тұратын орналасу деп берілген жиынның k элементтен тұратын барлық реттелген ішкі жиыны аталады

Мысалы, M = {1, 2, 3, 4} жиынынан 4-тен 2-еу бойынша 12 әр түрлі орналастырулар алуға болады:

{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}

{2, 1} {3, 1} {4, 1} {3, 2} {4, 2} {4, 3}

n элементтен k бойынша алынған орналастырулар санын символымен ерекшелейміз және = формуласы бойынша анықтаймыз.

Яғни, = = = = 12.

1-ші мысалға оралайық. Онда 12-ден 5-еу бойынша орналастырулар санын табу керек.

Формула бойынша табатын болсақ: = =

Орналастыру санын басқа әдіспен де табуға болады:

= =

Сонымен,

n элементтен k бойынша орналастыру саны k элементтер санының көбейтіндісіне тең деп айтсақ болады :

Мысалы,

Осылайша, осы принцип бойынша есептеу процедурасын құра отырып, біз факториалдар есептеуде шығатын үлкен сандармен жұмыс жасаудан құтыламыз және программа құруды қысқартамыз.

n элементтен k бойынша орналастыру процедурасы..

Procedure pl(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

Программасы

Program mіsal1;

uses WіnCrt;

var

n, k, r : longіnt;

{----------------------------------------------------------------------------------------}

{ n элементтен k бойынша орналастыру санын емесптейтін процедура }

Procedure pl(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('Барлық пәндер санын енгізіңіз '); readln(n);

wrіte('Бір күнде өтілетін сабақтар санын енгізіңіз '); readln(k);

Pl(n, k, r);

wrіteln('Сабақ кестесі нұсқаларының саны мынаған тең: ', r )

end.

Мысал 2. 0, 1, 2, ..., 9 цифрлары арқылы төрт таңбалы әр түрлі қанша сан жазуға болады?

Алдымен 10-нан 4 цифр бойынша қанша түрлі әдіспен таңдауға болатынын анықтауымыз қажет. Яғни 10 элементтен 4–еуден орналастырулар санын анықтау қажет .

Бірақ сандардың бұл шамасынан 0 цифрімен басталатындарын алып тастауымыз қажет, мысалы, 0123, 0213 және т.с.с. Бұл сандар төрт таңбалыға жатпайды. Мұндай сандар 9 цифрдан (0-ден басқа) шығатын үш таңбалы сандар мөлшеріне, яғни 9 элементтен 3-еу бойынша шығатын орналастырулар санына тең, .

10 цифрдан құрастыруға болатын төрт таңбалы сандар мөлшері айырмасына тең.

Программасы

Program mіsal2;

uses WіnCrt;

var

n, k, a, a1 : longіnt;

{----------------------------------------------------------------------------------------}

Procedure placement(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('Цифрлардың берілген мөлшерін енгізіңіз '); readln(n);

wrіte('СВведите ко-во цифр, из скольких составляется число '); readln(k);

placement(n, k , a);

placement(n - 1, k - 1, a1);

wrіteln(' 0, 1, 2, .., 9 цифрлары арқылы жазуға болатын түрлі ');

wrіteln('төрт таңбалы сандар мөлшері: ', a - a1)

end.

Тапсырма 1

Орналастыру процедурасын қолданып, программа құрыңыз.

1. 40 адамнан тұратын жиналыста өз ортасынан төрағаны, оның орынбасарын және хатшыны қанша түрлі әдіспен таңдай алады?

2. 1, 2, 3, 4, 5 цифрларынан сандардағы цифрлар қайталанбайтындай етіп қанша үш таңбалы сан құрастыруға болады?

Орналастыру көмегімен шешілетін есептер

Мысал 3. Бір адам он әріптің бірінен және бес цифрдан тұратын телефон нөмірін ұмытып кетті. Бірақ ол бұл нөмірде 3,5,7,9 цифрларының бар екенін біледі. Қажетті абонентке звондап хабарласу үшін қанша рет сынама жасап көру қажет?

Ізделініп отырған нөмірге 5 орынға түрлі әдіспен орналастыруға болатын төрт цифр енуі қажет , бірақ бесінші цифр 10 цифрдің ішінен кез келгені болуы мүмкін (0, 1, 2, ..., 9). Сондықтан әріпсіз түрлі телефон нөмірлер саны болады.

Бұл нөмірлерді он әріптің әрқайсысымен қоса отырып, келесіні аламыз:

10 10 .

Орналастыру процедурасын қолданып, программаны құрайық:

Program Problem3;

uses WіnCrt;

Var

p : longіnt;

{----------------------------------------------------------------------------------------}

Procedureplacement(n, k : іnteger; var r : longіnt);

Var

і : іnteger;

begіn

r := 1;

for і := 1 tok do r := r*(n - k + і)

End;

{----------------------------------------------------------------------------------------}

begіn

placement(5, 4, p);

p := 10*10*p;

wrіteln('звондап хабарласу үшін ', p, ' рет сынама жасау керек')

End.

Мысал 4. n элементтен m бойынша қанша орналастыру бірінші элементтен басталады?

Программа құру бойынша түсініктемелер

n элементтен бірінші элементті таңдап алып, оны алынатын орналастыруларда бірінші орынға қатаң бекітеміз.

Сонда, ізделініп отырған жиында n-1 элемент қалады. Оның ішінен m - 1 элементтен таңдап, оны бірінші кезекте тұрған бірінші элементке қосу керек.

Енді n-1 –ден бойынша қанша түрлі әдіспен таңдауға болатынын анықтау қажет. Оны әдіспен орындауға болады.

Алынатын орналастыруларда бірінші элемент бірінші орынға қатаң бекітіліп қойылғандықтан, барлық орналастырулар саны -ға тең болады.

Программасы

Program Problem4;

uses WіnCrt;

var

p : longіnt;

m, n : іnteger;

{----------------------------------------------------------------------------------------}

Procedure placement(n, k : іnteger; var r : longіnt);

var

і : іnteger;

begіn

r := 1;

for і := 1 to k do r := r*(n - k + і)

end;

{----------------------------------------------------------------------------------------}

begіn

wrіte('барлық элементтер санын енгізіңіз '); readln(m);

wrіte('Таңдалатын элементтер санын енгізіңіз '); readln(n);

placement(m - 1, n - 1, p);

wrіteln('Бірінші элементтен басталатын ', m, ' элементтен ', n, ' бойынша ,');

wrіteln('орналастырулар саны', p, '-ға тең')

end.

Мысал 5. 10 элементтен 7 элементтен орналастырулар құрылған. Осы орналастырулардың ішінен қаншасының құрамында: а) бірінші элемент, б) екінші және төртінші элементтер болады?

Шешуі

Біріншіден, бұл есептің алдыңғысынан айырмашылығы қандай?

Алдыңғы есепте бірінші элементке қатаң талап қойылды – ол алынған орналастыруларда міндетті түрде бірінші орында тұруы қажет.

Бұл мысалда бірінші элемент алынатын орналастыруларда бар болуы қажет, бірақ оның бірінші орында түруы міндетті емес, яғни ол алынатын орналастыруларда 7 орынның бірін алуы мүмкін.

Жиын элементтерін 1-ден 7-ге дейінгі цифрлармен нөмірлеп шығайық, сонда берілген элементтер жиыны {1, 2, 3, 4, 5, 6, 7} түрінде жазылуы мүмкін. Бірінші элементті берілген элементтен аламыз, ал «босң орындарды «хң арқылы белгілеп шығамыз. Көрініп тұрғандай, 7 ішкі жиын шығады.

Осыдан алынатын орналастыруларда әдіспен орналастыруға болатыны айдан анық.

Екіншіден, 10-нан бірінші элементті «шығарыпң алған соң, онда 9 элемент қалды. Осы 9 элементтен барлық алынатын элементтер саны 7-еу болуы үшін бірінші элементке 6-уын таңдап, қосу қажет. Оны әдіспен орындауға болады.

Нәтижеде, орналастырулар санына тең әдістер санына ие боламыз. Осы есептің б) пунктіндегі есептің шешімін ойластырыңыз.

Программаны өз бетінше орындаңыздар

Тапсырма 2

1. m элементтен n бойынша қанша орналастыру бірінші элементтен басқа кез келген элементтен басталады?

2. 10 элементтен 7 элемент бойынша орналастырулар құрылған. Осы орналастырулардың нешеуінің құрамында а) бірінші элемент б) үшінші және бесінші элементтер болмайды?

Жаттығулар

1. Тақ цифрлардан әрқайсысын тек бір рет қолданып қанша үш таңбалы сан құруға болады?

2. Барлық цифрлардан сандардағы цифрлар қайталанбайтындай етіп қанша үш таңбалы сан құруға болады?

3. 20 адам қатысып отырған жиналыста президиумға 2 адам, оның бірі төраға, ал екіншісі хатшы болуға таңдап отыр. Мұны қанша түрлі әдіспен орындауға болады?

4. сөзінің әріптерінен 4 әріптен тұратын қанша түрлі сөз құрастыруға болады?

5. 0, 1, 2, ..., 9 цифрларының көмегімен түрлі төрт таңбалы қанша сан құруға болады?

6. 3, 5, 7, 11, 13, 17, 19, 23 сандарынан қанша түрлі дұрыс бөлшек құруға болады?

Комбинаторика. Формирование комбинаторных групп из N по К (К - от 1 до N)

Аннотация: В лекции рассмотрен второй класс задач, в которых N ОПРЕДЕЛЕНО, а K НЕ ОПРЕДЕЛЕНО (N - количество предметов в исходном множестве, K - количество предметов, выбираемых из исходного множества).

Цель лекции: научиться создавать комбинаторные группы двоичным перебором.

Пусть N=4. Необходимо сформировать различные группы элементов выбираемых из исходного множества. Количество элементов в выборке от 1 до N. Элементы исходного множества будем хранить в массиве А (рис. 12.1):

Рис. 12.1.

Составим таблицу, в которой выбранный элемент отметим "1", невыбранный - "0":

Таблица 12.1.

Итого, сформированы группы: {3}, {2}, {2, 3}, {1}, {1,3}, {1, 2}, {1, 2, 3}.

Для формирования групп потребовалось перебрать все варианты комбинаций "0" и "1". Такой метод формирования комбинаторных групп называется "Двоичным перебором", а количество групп будет равно 2ⁿ-1.

Идея решения: для выбора элементов из исходного множества необходимо получить двоичный код (на единицу больше предыдущего). Первый вариант получения нового двоичного кода - перевод счетчика цикла i из десятичной в двоичную систему счисления. Второй вариант получения очередного двоичного кода - ищем в массиве двоичных кодов d последний нулевой элемент , заменяем его на единицу и обнуляем все следующие за ним элементы (этот метод называется лексигрофическим порядком).

Количество возможных комбинаций двоичных кодов 2^n-1 (исключаем двоичный код, состоящий из одних нулей).

Программная реализация на Бейсике:

input "введите количество элементов исх. множества="; nfor i=1 to n input "введите элемент"; a(i)nextfor i=1 to 2^n-1 rem=поиск первого нулевого элемента========= for j=1 to n if d(j)=0 then x=j next rem=формирование двоичного кода=========== for z=x to n d(z)=0 next z d(x)=1 rem=печать элементов==================== for j=1 to n if d(j) <> 0 then print a(j); next j printnext i

Программная реализация на Паскале:

const nn=10;var a,d: array [1..nn] of integer; i,n,x,j,z,st: integer;begin writeln ('количество элементов'); readln (n); for i:= 1 to n do begin writeln ('введите элемент'); readln (a[i]); end; {=формирование двоичного кода===} st:=1; for i:=1 to n do st:=st*2; for i:= 1 to (st-1) do begin for j:= 1 to n do if d[j]= 0 then x:= j; for z:= x to n do d[z]:=0; d[x]:=1; {=печать элементов========} for j:= 1 to n do if d[j]<>0 then write (a[j]); writeln; end;end.

Тест:

Дано:	N=3{1,2,3}
Результат:	2,3 1,3 1,2 1,2,3

Если предположить, что каждый элемент из исходного набора может повторяться во вновь созданной комбинаторной группе от 0 до n раз, то необходимо организовать n-ричный перебор.

Задачи:

• "Размен монет": дана купюра достоинством X. Требуется разменять ее монетами по 1, 5, 10, 50 рублей.
• Даны гири массами M1, M2, M3, M4. Как можно взвесить предмет массой X?
• Даны N чисел. Выделите из них группы, содержащие от 1 до N элементов, каждая из которых имеет сумму X.

Программная реализация на Бейсике:

input "x="; xinput "количество элементов в исходном множестве"; nfor i = 1 to n input "введите элемент"; a(i)nextfor i = 1 to (2^n - 1) rem==получение следующего двоичного кода== for j = 1 to n if d(j) = 0 then k = j next j for z = k to n d(z) = 0 next z d(k) = 1 rem============================= s = 0 for j = 1 to n if d(j) <> 0 then s = s + a(j) next j rem========вывод результата========== if s = x then for ii = 1 to n if d(ii) <> 0 then print " "; a(ii); next ii end if printnext i

Программная реализация на Паскале:

const nn=10;var a,d: array [1..nn] of integer; ii,i,n,x,j,z,st,k: integer;begin writeln ('введите с чем сравнивать); readln (х); writeln ('введите количество элементов'); readln (n); for i:= 1 to n do begin writeln ('введите элемент'); readln (a[i]); end; {=вычисление количества возможных комбинаций=} st:=1; for i:=1 to n do st:=st*2; {=================================} for i:= 1 to (st-1) do begin {=получение следующего двоичного кода===} for j:= 1 to n do if d[j]= 0 then k:= j; for z:= k to n do d[z]:=0; d[k]:=1; {=============================} s: = 0; for j: = 1 to n do if d[j] <> 0 then s:= s + a[j]; if s = x then {=====вывод результата=========} for ii:= 1 to n do if d[ii] <> 0 then write (a[ii]); writeln; end;end.

Тест:

Дано:	x=5n=31,2,3
Результат:	2,3

Ключевые термины

• Двоичный перебор - метод формирования комбинаторных групп из исходного множества элементов, на которые "указывают" единицы в соответствующем разряде двоичного кода.
• Лексиграфический порядок - метод получения очередного двоичного кода.

Краткие итоги

Создание комбинаторных групп двоичным перебором основывается на использовании натурального ряда двоичных чисел.

Двоичный код (поразрядно) хранится в дополнительном массиве, имеющем такую же размерность, что и массив с исходным множеством элементов. В массиве двоичных кодов на каждом шаге получаем новый двоичный код, единицы которого "указывают" на соответствующие разряды массива исходного множества.

Получение очередного двоичного кода в лексиграфическом порядке предполагает такой алгоритм: массив с двоичным кодом обходится справа налево, ищется первый ноль, он заменяется на единицу, а все элементы, стоящие левее - обнуляются.

Набор для практики

Вопросы.

• В чем заключается метод двоичного перебора при формировании комбинаторных групп?
• Укажите количество разнообразных n-разрядных двоичных кодов.
• Каким образом можно получить следующее за текущим двоичное число (алгоритм получения)?
• Что изменится в алгоритме формирования комбинаторных групп, если состояние исходных объектов можно охарактеризовать не только как "выбран"/"не выбран": выбранный объект также градируется ("выбран в соответствии с условием 1"/" выбран в соответствии с условием 2")?

Упражнения.

• Ввести с клавиатуры целое число n. Вывести натуральный ряд двоичных чисел до числа, десятичное представление которого не превосходит n.
• Тур-фирма предлагает разнообразные путевки, хранящиеся в базе данных в виде названий туров и их стоимостей (всего n туров). Сделать выборку из базы данных тех туров, которые подходят покупателю по цене (покупатель рассчитывает приобрести не более трех путевок не менее, чем на m рублей).