Разбиения

Число разбиений (порядок записи подмножеств - элементов разбиения считаем значимым) n-элементного множества на k £ n непустых подмножеств равно:

.

Общее число разбиений:

.

[Донской В.И. Дискретная математика. Уч. пос. – Симферополь, "Сонат", 2000.- 360 с.]

Процедура partitions позволяет получить все разбиения заданного множества на не пустые подмножества. Порядок записи подмножеств - элементов разбиения считается значимым.

Искомые разбиения представлены в виде двухмерного массива – одномерного массива одномерных массивов типа vector. Используются структура vector из стандартной библиотеки STL. Процедура print(S) выводит на экран очередное разбиение.

Приведенная реализация является рекурсивной. В исходном множестве поочередно выбирается подмножество. В оставшейся части множества опять поочередно выбирается подмножество и т.д. При исчерпании элментов исходного множества очередное разбиение получено и выполняется переход к формированию следующего разбиения.

Переменная b типа unsigned long используется для битового представления очередного подмножества, отсюда имеем максимальный размер исходного множества для приведенной реализации - 32. Рассматривать исходное множество большего размера не имеет смысла, т.к. число разбиений оказывается слишком велико для любого численного анализа.

#include <syst.h>

#include <vector.h>

void partitions(vector<int> & A) // A – исходное множество, затем оч. подмнож.

{ static M; // Номер очередного разбиения

int i, n = A.size();

unsigned long b, t;

vector<int> R, C;

static vector < vector<int> > S;

for (b=1; b < pow(2,n); b++)

{ t=0x0001; R=C=vector<int>();

for (i=0;i<n;i++) { if (b&t) R.push_back(A[i]);

else C.push_back(A[i]);

t <<= 1;

}

S.push_back(R);

if (C.empty()) { M++; printf("%4d -> ", M);

print(S); return;

}

partitions(C);

S.pop_back(); S.pop_back();

}

}