Реферат: Генерация комбинаторных объектов

0100 C

0101 AC

0110 BC

0111 ABC

1000 D

1001 AD

1010 BD

1011 ABD

1100 CD

1101 ACD

1110 BCD

1111 ABCD

Таким образом, всего имеется 16 различных подмножеств множества из 4-х элементов. В общем случае множество всех подмножеств множества из N элементов содержит 2N (два в степени N) элементов.

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

Формируем массив, состоящий из N нулей - и рассматриваем его как пустое множество. Таким образом, начальное значение текущего подмножества - пустое множество.

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

Справа (от первого элемента массива к последнему) ищем первое число, равное нулю.

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

Если же элемент равный 0 найден, то он заменяется на 1, а все числа справа от него (если таковые имеются) заменяются на нули.

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

Ввод (N)

Обнуление массива B из N+1 элемента

Вывод (Пустое множество)

Пока B[N+1]=0

i=1

Пока B[i]=1 делать B[i]=0, i=i+1

B[i]=1

Вывод (множества, определяемого массивом B)

Ниже приводится текст программы, которая считывает N - число элементов в множестве и выводит на экран множество всех подмножеств обозначая элементы соответствующими по порядку латинскими буквами: