Void main()

{ int i = 0, j, n, p;

unsigned long l, number;

printf("n=");

scanf("%d", &n); // ввести число элементов исходного множества

int* d = new unsigned char[n]; // Массив – бинарный код подмножества

number = 0x00000001 << n; // number - число всех подмножеств

printf("number=%ld \n", number);

for (j = 0; j < n; j++) d[j] = 0; // инициализация массива d

for (l = 0; l < number;l ++)

{ p = 0; i++; printf("%d ", i); // номер очередного подмножества

while(d[p] == 1) d[p++] = 0; // Установка первых единичных эл-тов в 0

d[p] = 1; // Установка след. эл-та в 1

for (j = 0; j < n; j++) if (d[j] == 1) printf("%d ",j);

puts(""); // вывод на экран очередного подмножества

}

delete[] d;

}

Множество представлено массивом B.

int next_subset(int n, int r, int*& B)

{ int i, k, q = 1;

static int* A;

static m;

m++;

if (m == 1) { A = new int[n];

for (i = 0; i < n; i++) A[i] = i;

B = A; return m;

}

K = r - 1;

while (q) { A[k]++;

if (A[k] + r – k – 1 < n) q = 0;

else k--; if (k < 0) { m = 0; break; }

for (i = k + 1; i < r; i++) A[i] = A[i-1] + 1;

}

if (m == 0) delete[] A;

else B = A;

return m;

}

Работу функции next_subset проиллюстрируем следующим примером. Пусть имеем 5-элементное множество: X = {0,1,2,3,4}. Первые несколько подмножеств для r=3 будут такими:

X = {0,1,2}

X = {0,1,3}

X = {0,1,4}

X = {0,2,3}

X = {0,2,4}

X = {0,3,4}

X = {1,2,3}

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

Для того, чтобы получить на экране все подмножества из 8-элементного множества
A = {0,1,2,3,4,5,6,7} можно воспользоваться такой программой:

const n=8;

Void main()

{ int i, m, r, N = 0;

int* A;

for (r = 0; r <= n; r++)

{ while (m = next_subset(n, r, A)) { printf("%2d ", m);

for (i = 0; i < r; i++) printf("%d ", A[i]);

printf("\n");

N++;

}

}

printf("N=%d \n", N);

if (N == 256) puts("Test was passed OK");

else puts("Test was Failed");

}