atlas  0.6
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