Головна |
є n різних предметів. Скільки з них можна скласти k-расстановок? При цьому дві розстановки вважаються різними, якщо вони або відрізняються один від одного хоча б одним елементом, або складаються з одних і тих же елементів, але розташованих в різному порядку. Такі розстановки називають розміщеннями без повторень, А їх число позначають. при складанні k -Розміщення без повторень з n предметів нам треба зробити k виборів. На першому кроці можна вибрати будь-який з наявних n предметів. Якщо цей вибір вже зроблено, то на другому кроці доводиться вибирати з решти n-1 предметів. на k -м кроці n-k-1 предметів. Тому за правилом твори отримуємо, що число k -Розміщення без повторення з n предметів виражається наступним чином:
наприклад, При генерації всіх розміщень з 5 елементів по 3 в разі, коли самі елементи позначені латинськими буквами А, 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
аналіз алгоритмів | алгоритм поєднання
Лекція 20. Алгоритми генерування перестановок, безлічі всіх підмножин, к-елементних підмножин множини, розбиття множин. | проблема подання | класи алгоритмів |