Scine::Molassembler::Shapes::Partitioner Class Reference

Given S * E distinguishable objects, this class helps enumerate all partitions into S groups of size E. More...

#include <Partitioner.h>

Public Member Functions
	Partitioner (unsigned s, unsigned e)
	Constructor. More...
bool	next_partition ()
	Advance underlying state to the next partition. More...
std::vector< std::vector < unsigned > >	partitions () const
	Generate sets of element indices within their respective partitions. More...
unsigned	s () const
	Number of groups.
unsigned	e () const
	Number of elements per group.
const std::vector< unsigned > &	map () const
	Access to underlying flat map from element index to group index.

Static Public Member Functions
static bool	isOrderedMapping (const std::vector< unsigned > &mapping)
	Check whether the sets as specified by the mapping are ordered. More...

Private Attributes
unsigned	S
	Number of groups.
unsigned	E
	Number of elements per group.
std::vector< unsigned >	mapping
	Flat map from element index to group index.

Detailed Description

Given S * E distinguishable objects, this class helps enumerate all partitions into S groups of size E.

The challenge with writing such a class is getting complexity less than \(\Theta((S\cdot E)!)\) considering that the sets themselves are indistinguishable. For instance, for the trivial example \(S = 2, E = 2\), there are only three distinct solutions:

• {1, 2}, {3, 4}
• {1, 3}, {2, 4}
• {1, 4}, {2, 3}

There are two orders at play here, the sets are lexicographically ordered and the elements within them are too.

Constructor & Destructor Documentation

Scine::Molassembler::Shapes::Partitioner::Partitioner	(	unsigned	s,
		unsigned	e
	)

Constructor.

Parameters

s	Number of groups
e	Number of elements per group

Precondition

s is not zero and e is not zero

Complexity \(\Theta(S\cdot E)\)

Member Function Documentation

static bool Scine::Molassembler::Shapes::Partitioner::isOrderedMapping ( const std::vector< unsigned > &  mapping )

static

Check whether the sets as specified by the mapping are ordered.

Complexity \(O(S\cdot E)\)

bool Scine::Molassembler::Shapes::Partitioner::next_partition

(

)

Advance underlying state to the next partition.

Complexity \(O(S\cdot E)\)

Returns

whether the underlying state reflects a new, valid partition

std::vector< std::vector<unsigned> > Scine::Molassembler::Shapes::Partitioner::partitions

(

)

const

Generate sets of element indices within their respective partitions.

Complexity \(\Theta(S\cdot E)\)

---

The documentation for this class was generated from the following file:

• Molassembler/Shapes/Partitioner.h