Задача 3.
Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}.
Пример: N=3, k=2,
подмножества {1,2}, {1,3}, {2,3}.
|
Решение задачи 3.
Воспользуемся следующим алгоритмом генерации сочетаний по k элементов из множества A:
В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число k). В качестве начальной конфигурацией возьмем следующую: B[j]=j, j=1,...,k.
Ищем B[j] с максимальным индексом j такое, что
B[j]<n+j-k,
увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значениями элементов массива B[m], m>j, последний элемент B[k] не превосходил бы n). Если такого B[j] не существует, то генерация сочетаний для данного k закончена.
|
