13.4. Генерація підмножин

Задача

Задано пару додатних цілих чисел n,r, причому r  n. Потрібно вивести на екран всі r-елементні підмножини із множини чисел, що належать відрізку [0, n-1].

Алгоритм

Для збереження елементів поточної підмножини будемо застосовувати r-елементний масив A[0], A[1], ... , A[r-1]. Елементи поточної підмножини будемо подавати у монотонно зростаючому порядку. Не дуже важко зрозуміти, що у такому разі елемент робочого масиву A[k] не може отримати значення більше, ніж n-r+k . Алгоритм побудуємо наступним чином.

1. Нехай k = r-1.

2. Збільшуємо A[k] на одиницю.

Якщо A[k]  n-r+k , виконуємо присвоєння A[i+1]=A[i]+1 для всіх i від k+1 до r-2 , тобто до кінця масиву А. Масив А буде вміщувати чергову шукану підмножину. Вивести її на екран. Перейти до п.1.

Якщо ні, то зменшити k на одиницю.

Якщо k<0 , то завершити процес.

Якщо ні, то перейти до п.2.

Програмна реалізація наведеного алгоритму для довільних n,r наведена нижче. Для збереження поточної підмножини A застосовується динамічний масив.

// Приклад 1

#include <syst.h>