Three Representations for Set Partitions

José Torres-Jiménez

doi:10.1109/ACCESS.2021.3061217

Three Representations for Set Partitions

2021-01-01

1

OA

AI

J

José Torres-Jiménez *

C

Carlos Lara-Álvarez

A

Alfredo Cardenas-Castillo

DOI：10.1109/ACCESS.2021.3061217

原文链接

查看原文

摘要

En 中文

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

Keyword:

Licenses

Redundancy

Partitioning algorithms

Genetic algorithms

Web mining

Self-organizing feature maps

Maintenance engineering

Bell numbers

factoradic number system

restricted growth strings number system

stirling numbers of the second kind

Eulerian numbers

Three Representations for Set Partitions

摘要

AI总结

期刊

机构

引用论文