Просматриваем все биты от 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 есть всегда некоторое целое число, то для формирования всех подмножеств можно формировать числа от нуля до 2n-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);