Как, имея b, получить подмножество элементов из А?

Просматриваем все биты от 0-го до (n-1)-го из b, выводим элементы а[i], соответствующие единичным битам.

Void f1 (int A[], int n, unsigned int b)

{//вывод элементов подмноджества, заданного строкой b

cout<<’\n’;

...

.....

int m=1;

b:

n-1 n-2............. 3 2 1 0

for (int i=0; i<n; i++)

{if (b&m) cout<<а[i]<<” ”;

m<<=1;

}

cout<<’\n’;

}

Void f2 (int а[ ], int n, unsigned char b [ ])

{//вывод элементов подмножества, заданного массивом b.

int j=0, m=0;

cout<<’\n’;

for (int i=0; i<n; i++)

if (b[j] & 1<<m)

{ cout<<а[i]<<” ”;

m++;

if (m==8){m=0; j++;}

}

cout << ’\n’;

}

Как сформировать все подмножества из А?

Так как представление в строке b есть всегда некоторое целое число, то для формирования всех подмножеств можно формировать числа от нуля до 2ⁿ-1(начать с нуля и добавлять по 1 на каждом шаге), их двоичные представления дадут все подмножества n-элементного множества.

unsigned int b=0, k=(1<<n)-1; //k=0000…..0111111111

while (b<k) // n

{b=b+1;

//обработка подмножества, заданного битовой строкой b

..........

}

В этом алгоритме последовательно получаемые подмножества могут сильно отличаться друг от друга: после (n-1)-элементного множества (которому соответствует число 01111…..1) идёт одноэлементное множество(отвечающее числу 1000……0). Это часто неудобно.

....000....000001

....000.... 000010

....000.... 000011

................

....000.... 011111

....000....100000

.... 000....100001

.... 000.... 100010

..................

.... 000... 0111100

.... 000... 1000111

..................

И т.д.

Пример 1.

Рассмотрим алгоритм генерации k-элементных подмножеств множества из n элементов, т.е. последовательного формирования возрастающих по значению битовых строк с k единицами.

//Nelset.cpp k-элементные подмножества,

// маска - слово

#include <iostream>

#include <fstream>

#include <iomanip>

#include <math.h>

using namespace std;

//Дана совокупность не более n целых чисел

//и число k. Выбрать все подмножества из k

// простых чисел.

//Все подмножества (k – элементные) записать в файл.

const int L=32; // n=31 элемент +1

ifstream fin;

ofstream fout;

// прототипы функций

void print (ofstream &fout, int a[], int n, unsigned int b);

bool prost (int a);