next up previous contents
Next: Internals Up: Graph Operations Previous: Commonalities Among Combinatorial Objects

Permutations

A permutation of a set of objects is a particular arrangement of them. Permutations can be throught of as either arrangements, or an operation which rearranges a set of objects. Permutations of the numbers $1,\ldots,n$ can describe a particular arrangment of arbitrary objects (and hence are an operation). The Permutation object describes such an arrangement, and can be applied to a Sequenceof typed objects to obtain a permutation of the latter.

1. Creation






Permutation permutation_name(int n)



Create the identity permutation $1,\ldots,n$.









Permutation<Item> permutation_name(Set s)  
Permutation<Item,Structure> permutation_name(Set s)  



Create a permutation whose elements are the elements of set s. The initial permutation corresponds to the sorted order of these element Structure is the Container implementation used to maintain the permutation's local copy of s.







2. Operations






Permutation& random ()



Rearrange the permutation in random order.









int rank ()



Return the rank of the permutation, ie. the position of the permutation in lexicographic order. The ranks run from 0 to n!-1.









Permutation& unrank (int m)



Unrank the mth permutation, ie. change the current permutation to the mth permutation in lexicographic order.









Permutation& next ()



Change the permutation to its successor in lexicographic order.









Permutation& previous() 



Change the permutation its predecessor in lexicographic order.









Permutation& first ()



Change the permutation to the first permutation in lexicographic order, the identity permutation.









Permutation& last ()



Change the permutation to the last permutation in lexicographic order, the reverse of the identity permutation.









void display ()



Display the permutation in human-readable form.









Bool operator==(Permutation& p)  
Bool operator>(Permutation& p)  
Bool operator>=(Permutation& p)  
Bool operator<(Permutation& p)  
Bool operator<=(Permutation& p)  
Bool operator!=(Permutation& p)  



Compare two permutations according to lexicographic order.









friend istream& operator>> (istream& s,Permutation p)



Input p from input stream s.









friend ostream& operator<< (ostream& s,Permutation p)



Output p to output stream s.









Permutation& operator=(Permutation p)  
Permutation& copy(Permutation p)  



Creates a copy of permutation p.









Type operator[]  (int i)



Return the value of the ith element of the permutation. If the permutation was constructed from the element of the set, an element is returned, otherwise it is an integer from 1 to n.









int size ()



Return size of the permutation







Permutation objects can be used to obtain permutation of typed objects like vertices and edges as follows. The class SetFuncs, provides the necessary interface. Note that several of the methods in this class produces results of exponential in the size of the input.


Set<Sequence<Item> > SetFuncs<Item>::cartesianProduct (const Set<Item>&s, const Set<Item>&s2);



Constructs and returns the set of all ordered pairs in the cartesian product of s and s2.









Set<Sequence<Item> > SetFuncs<Item>::cartesianProduct (const Set<Item>&s1, const Set<Item>&s2)



Constructs and returns the set of all k-subsets of s.









Set<Set<Item> > SetFuncs<Item>::choose (const Set<Item>&s, int k)



Constructs and returns the set of all k-subsets of s.









Set<Set<Item> > SetFuncs<Item>::powerSet (const Set<Item>&s)



Constructs and returns the set of all possible subsets s.









Sequence<Item> SetFuncs<Item>::permutation (const Set<Item>&s, const Permutation& p);



Permutes the elements of s into the order specified by permutation p.









Sequence<Item> SetFuncs<Item>::permutation (const Array<Item>&a, const Permutation& p);



Permutes the elements of a into the order specified by permutation p.









Set<Sequence<Item> > SetFuncs<Item>::permutations (const Set<Item>&a);



Returns a set of all permutations of s.








next up previous contents
Next: Internals Up: Graph Operations Previous: Commonalities Among Combinatorial Objects
RHS Linux User
1/26/1998