Three Representations for Set Partitions

摘要: The Set Partitioning Problem (SPP) aims to obtain non-empty disjoint subsets of objects such that their union equals the whole set objects, and partition meets some prespecified criteria. ubiquity SPP is impressive, given it has a lot theoretical practical motivations. In side, study closely related Bell numbers, Stirling numbers second kind, integer partitions, Eulerian Restricted Growth Strings (RGS), factoradic number system, power calculations, etc. intimately classification problems, clustering reduction dimensionality so on. this work, three representations for instances are presented, these use: system with fixed base. Two cases will be presented: where unbounded (i.e. can objects); less than objects. Bidirectional mappings between introduced, also mapping among base defined. Given, used solve using exact, greedy, metaheuristic algorithms, require do small changes one possible solution and/or recombination two solutions, definitions mutation operators shown. order motivate use particular SPP, was decided present application an instance integers problem (SPIP) simple genetic algorithm.