Charles V. Schaefer, Jr. School of Engineering and Science
 
 
SES Home » Science Departments » Algebraic Cryptography Center » Software

Software

The CRAG Software Library FAQ

// Copyright (C) 2006 Aleksey Myasnikov
// Contents: Example for class Word
//
// Principal Authors: Aleksey Myasnikov
//
// Revision History:
//


#include "Word.h"
#include 
#include 
#include 
#include 
#include 

using namespace std;



int main()
{
  //---------------------------------------------------------------------------//
  //------------------------- Examples: Word ----------------------------------//
  //---------------------------------------------------------------------------//
  
  /*
    Reduced words are  represented  as a list of non-trivial integers list< int >.
    Each generator  x is represented by the unique number  n_x.
    For each x  it is assumed that n_{x^{-1}} = -n_x.
  */
  
  
 
// How do I create a word?
  
  // Create an empty word (identity)
  Word e;
  cout << "Create an empty word : " << e << endl;





  // Create a word from a vector of generators  , 
  // where xi is a positive or negative  integer s.t. 
  // abs(xi) = 1, ..., n and n is the rank of a group
  vector v(4,0); // 4 generators in the vector
  
  // Enter <1,1,-2,-2> which corresponds to a word x1^2 x2^-2 in 
  v[0] = 1; v[1] = 1; v[2] = -2; v[3] = -2; 
  





  // create a word from v
  Word wv(v);
  cout << "Create a word from a vector of generators : " << wv << endl;
  
  // Create a word from a list of generators  , 
  list l; // 4 generators in the vector
  
  // Create a list which corresponds to a word (x1 x2)^10 in 
  for (int i=0;i<10;i++){
    l.push_back(1); // append the first generator  (see below)
    l.push_back(2); // append the second generator
  }
  
  // create a word from l
  Word wl(l);
  cout << "Create a word from a list of generators : " << wl << endl;
  
  




 
// How do I add letters and subwords to a word
  

  // Multiply the word by a one-letter word defined by gen on the right. The result is being reduced.
  Word w_p = e;
  e.push_back(1);
  cout << "Concatenate " << w_p << " and x1 = " << e << endl;



  // Multiply the word by a one-letter word defined by gen on the left. The result is being reduced.
  w_p = e;
  e.push_front(2);
  cout << "Concatenate x2 and " << w_p << " = " << e << endl;



  // Multiply the word by a word on the right. The result is being reduced.
  w_p = e;
  e.push_back(wv);
  cout << "Concatenate " <<  w_p << " and  " << wv << " = " << e << endl;



  // Multiply the word by a word on the left. The result is being reduced.
  w_p = e;
  e.push_front(wv);
  cout << "Concatenate " <<  wv << " and  " << w_p << " = " << e << endl;
  




  
 
// How do I insert letters or subwords into a word


  // Insert a sequence of generators [B,E) into a word at th position 5
  Word w_tmp = wl;
  //  w_tmp.insert( 5 , wv.begin(),wv.end() );
  //  cout << "Insert :" << wl << " -> " << w_tmp << endl;
  



  // Insert a generator x5 into a word after the 5th letter
  w_tmp = wl;
  w_tmp.insert( 5,5 );
  cout <<  "Insert :" << wl << " -> " << w_tmp << endl;
  



  // Insert a sequence of generators [B,E) into a word before the second position
  w_tmp = wl;
  WordIterator wI = wl.begin();
  //  w_tmp.insert::const_iterator>( ++wI,wv.getList().begin(),wv.getList().end() );
  //cout <<  "Insert :" << wl << " -> " << w_tmp << endl;
  



  // Insert a generator x5 into a word before the second position
  w_tmp = wl;
  wI = w_tmp.begin();
  w_tmp.insert( ++wI,5 );
  cout <<  "Insert :" << wl << " -> " << w_tmp << endl;
  
  


 
// How do I replacing letters and subwords
  

  //Replace a generator at the second position by x10
  w_tmp = wl;
  wI = w_tmp.begin();
  w_tmp.replace( ++wI,5 );
  cout <<  "Replace :" << wl << " -> " << w_tmp << endl;


  
  // Replace a subword of a word starting at the second position by a word [B,E). 
  // The length of the word does not increase if [B,E) is longer than the terminal
  // segment of the word [it,end()). 
  //In that case terminal symbols of [B,E) are ignored.
  w_tmp = wl;
  wI = w_tmp.begin();
  //  w_tmp.replace::const_iterator>( ++wI,wv.getList().begin(), wv.getList().end() );
  // cout << "Replace :" << wl << " -> " << w_tmp << endl;
  
  


 
// How do I multiply words
  

  // Multiply two words. The result is reduced.
  cout << "Multiply :" << wv << " * " << wl << " = " << wv*wl << endl;
  
  // Multiply a word on the right by another word. The result is reduced.
  Word wmul(wv);
  wmul *= wl;
  cout << "Multiply : " << wmul << endl;;
  
  


 
// How to invert a word
  cout << "Inverse of " << wv << " = " << -wv << endl;
  cout << "Inverse of " << wv << " = " << wv.inverse() << endl;
  
  

 
// How to reduce words
  
  // Freely reduce a word.
  wv.freelyReduce( );
  
  // Freely reduce a segment of a word defined by [B,E).
  wv.freelyReduce( wv.begin(),wv.end() );
  
  // Cyclically reduce a word
  Word cw = wv*wl*-wv;
  cw.cyclicallyReduceWord();
  cout << "Cyclically reduce " << wv*wl*-wv << " = " << cw << endl;
  
  // Cyclically reduces a word and returns the corresponding conjugator.
  Word conjugator;
  cw = wv*wl*-wv;
  cw.cyclicallyReduceWord(conjugator);
  cout << "Cyclically reduce " << wv*wl*-wv << " = " << cw << endl;
  cout << "Conjugator " << conjugator << endl;
  
  // Returns the cyclically reduced word. The original word is unchanged
  cout << "Cyclically reduce " << wv*wl*-wv << " = " << (wv*wl*-wv).cyclicallyReduce(  ) << endl;
  
  // Returns the cyclically reduced word and the corresponding conjugator. The original word is unchanged
  cout << "Cyclically reduce " << wv*wl*-wv << " = " << (wv*wl*-wv).cyclicallyReduce( conjugator ) << endl;
  cout << "Conjugator " << conjugator << endl;
  
  


 
// How do I iterate through the letters of a word
  
  // Iterate and print generators  of the word. 
  cout << "Generators of " << wv << " : " << endl;
  for (ConstWordIterator I=wv.begin();I!=wv.end();I++)
    cout << *I << " ";
  cout << endl;
  


  // Get a constant representation of a word as a list of integers corresponding to the generators.
  list< int > l1 = wv.getList( );
  cout << "List representation of " << wv << " is ";
  copy(l1.begin(),l1.end(), ostream_iterator( cout," "));
  cout << endl;
  

  // Get a representation of a word as a list of integers corresponding to the generators.
  // This allows direct manipulation with the representation (which requires caution).
  cout << "Change second letter of " << wv << " -> ";
  list< int >& l2 = wv.getList( );
  // change second letter to x10
  list::iterator lI = l2.begin();
  *(++lI) = 10;
  cout << wv << endl;
  
  
  
 
// How do I get words' length
  cout << "Length of " << wv << " is " << wv.length() << endl;
  


 
// How to extract subwords
  
  // Get an initial segment of the word of length 2
  cout << "Initial segment of " << wv << " is " << wv.initialSegment( 2 ) << endl;
  
  // Get a terminal segment of the word of length 2.
  cout << "Terminal segment of " << wv << " is " << wv.terminalSegment( wv.length() - 2 ) << endl;
  
  // Get a segment of the word defined 
  cout << "Segment of " << wv << " is " << wv.segment( 1,3 ) << endl;
  
  
 
// How do I compare words
  
  // Words are compared using lexicographical order 
  if (wv < wl )
    cout << wv << " is less than " << wl << endl;
  
  if (wv > wl )
    cout << wv << " is greater than " << wl << endl;
  
  if (wv == wl )
    cout << wv << " is equal to " << wl << endl;
  
  if (wv != wl )
    cout << wv << " is not equal to " << wl << endl;
  



 
// How do I cyclically shift a word

  // Shifts the word one position to the left
  Word wvls = wv;
  wvls.cyclicLeftShift();
  cout << "Cyclic left shift : " << wv << " -> " << wvls  << endl;


  // Shifts the word one position to the right
  Word wvrs = wv;
  wvrs.cyclicRightShift();  
  cout  << "Cyclic right shift : " << wv << " -> " <<  wvrs  << endl;
  
  



 
// How do I cyclically permute a word


  //Cyclically left-shift permute the word by 5 positions.
  cout << "Cyclically left-shift permute : "  << wv << " -> " << wv.cyclicallyPermute( 5 ) << endl;



  
  //Cyclically righ-shift permute the word by 5 positions.
  cout << "Cyclically right-shift permute : "  << wv << " -> " << wv.cyclicallyPermute( -5 ) << endl;
  

    
 
// How to generate a pseudo-random word
  
  // Generate a pseudo randomly reduced word of the length 10 in 2 generators
  cout << "Generate pseudo-random word of length 10 " <<  Word::randomWord( 2 , 10 ) << endl;
  
  // Generates a pseudo randomly reduced word of a length in [10,15] and  2 generators
  cout << "Generate pseudo-random word of length in [10,15] " <<  Word::randomWord( 2,10,15 ) << endl;
  


 
// How do I print a word

  // Print a word into the standard output stream. 
  // Default operator will print a word in alphabet x1 ... xN
  // See Alphabet class description too change the output alphabet 
  cout << "Print word : " << wv << endl;
  

 
// How do I input a word
  
  // Read a word from the standard input stream. 
  // Default operator will accept a word in alphabet x1 ... xN
  // See Alphabet class description too read words in arbitrary alphabet 
  cout << "Enter a word in generators x1, x2 ... " << endl
       << "Example: x1^2 [x2,x3^-2] (x5 x10)^-1 ; " << flush; 
  cin >> wv;
  cout << "You entered " << wv << endl;
  
  

 
// How to determine the power of the word as an element of a free monoid
  // Determines the power of the word (as an element of a free monoid, not as an element of a free group).
  Word base;
  cout << "Power of " << wv << " is " << wv.getPower( base ) << endl;
  cout << "Base : " << base << endl;
    
  
 
// How to check if a word contains a generator x2
  Word wr = Word::randomWord(5,5);
  cout << wr << ( wr.doesContain( 2 ) ? " contains " : " doesnot contain " ) << " x2 " << endl;
  
  
 
// How do I compute the exponent sum of a generator
  cout << "Exponent sum of x2 in " << wr << " is " << wr.exponentSum( 2 ) << endl;
  
 
// How do I compute a power of a word 
  // Compute wr^2
  cout << wr << " squared = " << wr.power(2) << endl;
  
 
// How to get the number of times a generator occurs in a word 
  // Print how many times x2 occur in wr 
  cout << "x2 occurs " << wr.isIn( 2 )  << " times in " << wr << endl;
  
  
  //! Compute the minimal equivalent word. 
  /*! permutableGenerators must be positive.
   */
  //Word minimalEquivalentForm( const set< int >& permutableGenerators , bool inverses , bool cyclicPermutations ) const;
  
  
}