atlas::partition Namespace Reference

Classes
class	Partition
class	PartitionIterator

Functions
template<typename F >
Partition	orbits (const F &, unsigned long, unsigned long)
template<typename F >
Partition	orbits (const F &a, size_t c, unsigned long n)

Function Documentation

template<typename F >

Partition atlas::partition::orbits	(	const F &	,
		unsigned	long,
		unsigned	long
	)

template<typename F >

Partition atlas::partition::orbits	(	const F &	a,
		size_t	c,
		unsigned long	n
	)

Constructs the orbit partition defined by the "action function" |a|. The type |F| is that of some function object that can be given a pair of |unsigned long| argument to produce an |unsigned long| result. The parameter |a| is such a function object; its first argument is the index $i$ of a generator in the range $[0,c[$, its second argument is the value acted upon, which is an integer in the range $[0,n[$; the result is again a value in the range $[0,n[$. It is assumed that for any fixed $i$, the function $a(i,)$ defines a permutation of $[0,n[$; thus the action parameter |a| defines $c$ generators of a permutation subgroup of $Sym([0,n[)$. The orbits for this action are returned as a |Partition| object in |pi|.

The algorithm is straightforward orbit generation, using a set $B$ of elements that have not yet joined any orbit, and a collection $S$ of elements that are in the current orbit but whose acted-upon images have yet to be generated. The set $B$ is represented as a bitmap on $[0,n[$, initially full, while $S$ is realized as a queue, initially empty.

While $B$ is not empty :

• move an element (the first one left) from $B$ to (the currently empty) $S$; start a new orbit with this element
• while $S$ is not empty :
  • x = S.top(); S.pop();
• for j in [0,c[ if x'=a(j,x) is in B: remove x' from B, push x' onto S, and add it to the current orbit