Генерация подмножеств для заданного множества.

//Генерация подмножеств заданного множества

//с ограниченным числом элементов

#include <iostream>

using std::cin;

using std::cout;

int main()

{

//Ввод размера множества

int n;

cin >> n;

if(n<=0)

return 0;

//Ввод предела размера подмножества

int size;

cin >> size;

if(size<=0 || size>n)

return 0;

//Создание и ввод множества

int *A = new int[n];

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

cin >> A[l];

//Создание массива для кода Грея

short *B = new short[n];

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

B[l]=0;

//Генерация всех подмножеств

int i=0,p,j,count;

do

{

//Подсчет количества элементов в подмножестве

count=0;

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

if(B[l]==1)

count++;

//Вывод подмножества, если количество его элементов равно size

if(count==size)

{

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

{

if(B[l]==1)

cout << A[l] << ' ';

}

cout << '\n';

}

//Генерация следующего кода Грея

i++;

p=0;

j=i;

while (j%2==0)

{

j=j/2;

p++;

}

if(p<n)

B[p]=1-B[p];

}

while (p<n);

delete[] B;

delete[] A;

return 0;

}

Генерация всех разбиений множества

//Генерация всех разбиений множества

#include <iostream>

using std::cin;

using std::cout;

//Вывод разбиения на экран

//a - исходное множество

//b - разбиение

void PrintPartition(int size, int *a, int* b)

{

//Проверка на существование массивов

if(a==NULL || b==NULL)

return;

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

int blocks=1;

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

if(b[i]>blocks)

blocks=b[i];

//Выводим каждое подмножество

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

{

for(int j=0;j<size;j++)

if(b[j]==i+1)

cout << a[j] << ' ';

if(i!=blocks-1)

cout << "| ";

}

cout << '\n';

}

//Помещает в элемент массива b с номером pos элементы от 1 до max

//и для каждого значения вызывает сама себя для следующей позиции массива

//а - исходное множество

//size - размер множества

void Partition(int pos, int max, int size, int *a, int *b)

{

//Проверка на существование массивов

if(a==NULL || b==NULL)

return;

//Если достигнут конец массива, то вывести разбиение

if(pos>=size)

{

PrintPartition(size,a,b);

return;

}

//Цикл по всем возможным вариантам для данной позиции массива

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

{

b[pos]=i+1;

//Переход к следующей позиции массива

//При этом, если данная позиция достигла максимума, то максимум следующей увеличивается на 1

if(i+1==max)

Partition(pos+1,max+1,size,a,b);

else

Partition(pos+1,max,size,a,b);

}

}

int main()

{

//Ввод размера множества

int n;

cin >> n;

if(n<=0)

return 0;

//Ввод множества

int *A = new int[n];

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

cin >> A[i];

cout << '\n';

int *B = new int[n];

//Генерация разбиений

//Начальное значение: нулевой элемент массива, максимальный индекс - 1

Partition(0,1,n,A,B);

delete[] A;

delete[] B;

return 0;

}

Генерация всех перестановок множества

//Генерация всех перестановок множества

#include <iostream>

using std::cin;

using std::cout;

//Множество

int* A;

//Размер множества

int size;

//Вывод множества

void Output()

{

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

cout<<A[i]<<" ";

cout<<"\n";

}

//Поменять местами два элемента множества

void Swap(int x,int y)

{

int temp = A[x];

A[x] = A[y];

A[y] = temp;

}

//Сгенерировать следующее разбиение

void Generate(int k)

{

//Генерация завершена, вывести множество

if (k==size)

{

Output();

}

else

{

//Продолжить генерацию

for(int j=k;j<size;j++)

{

Swap(k,j);

Generate(k+1);

Swap(k,j);

}

}

}

int main()

{

std::cout<<"Size: ";

std::cin>>size;

if(size<=0)

return 0;

//Заполнение множества

A = new int[size];

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

A[i] = i+1;

Generate(0);

delete[] A;

return 0;

}