atlas  0.6
Classes | Functions
atlas::partition Namespace Reference


class  Partition
class  PartitionIterator


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.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