Quelle  fndelt.c   Sprache: C

/* File fndelt.c.  Main program for fndelt command, which may be used
   to find semirandom elements of specified order (default 2) in a
   permutation group and to find the orders of all products of these elements
   or their number of fixed points.  Selected elements can be appended to a
   Cayley library, either in permutation or permutation group format.
   The format of the command is:

>       fndelt <options> <permGroup> <count>  <elt1>  <elt2>  <elt3> ...

   where the meaning of the parameters is as follows:

            <permGroup>: the permutation group from which involutions are to
                         be located.

            <count>:     the number of involutions to be located.

>           <invol1>:    (optional) First involution to be printed.

   The options are as follows:

      -o:n          Order of elements to find.

      -po           Find orders of all products of involutions.

      -f            Compute number of fixed points

      -i            Write permutations in image format

      -crl:<name>   Name of the Cayley library from which to read the group

      -s:<integer>  Seed for random number generator.

      -wg:<name>    Name of a Cayley library.  The group generated by the
                    selected permutations will be written to this Cayley
                    library.

      -wp:<name>    Name of a Cayley library.  The first element will be
                    be written to this Cayley library.   */


#include <stddef.h>
#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAIN

#include "group.h"
#include "groupio.h"

#include "errmesg.h"
#include "new.h"
#include "oldcopy.h"
#include "permut.h"
#include "readgrp.h"
#include "readper.h"
#include "randgrp.h"
#include "util.h"

static void verifyOptions(void);

GroupOptions options;

int main( int argc, char *argv[])
{
   char permGroupFileName[MAX_FILE_NAME_LENGTH+1] = "",
        permOutputFileName[MAX_FILE_NAME_LENGTH+1] = "",
        groupOutputFileName[MAX_FILE_NAME_LENGTH+1] = "",
        permGroupLibraryName[MAX_NAME_LENGTH+1] = "",
        permOutputLibraryName[MAX_NAME_LENGTH+1] = "",
        groupOutputLibraryName[MAX_NAME_LENGTH+1] = "",
        permOutputName[MAX_FILE_NAME_LENGTH+1] = "",
        groupOutputName[MAX_FILE_NAME_LENGTH+1] = "",
        outputObjectName[MAX_NAME_LENGTH+1] = "",
        prefix[MAX_FILE_NAME_LENGTH+1] = "",
        suffix[MAX_NAME_LENGTH+1] = "";
   char comment[60];
   Unsigned f, i, j, optionCountPlus1, successCount, numberOfInvolsToFind,
            orderToFind = 2, attemptCount, maxAttemptCount;
   BOOLEAN orderOption;
   unsigned long seed;
   unsigned long order;
   PermGroup *G, *involSubgroup;
   Permutation *newPerm, *prodPerm, *invol[100];
   BOOLEAN fixedPointsOption = FALSE, imageFormatFlag = FALSE;

   /* If there are no options, provide usage information and exit. */
   if ( argc == 1 ) {
      printf( "\nUsage: fndelt [options] permGroup numberOfElts [saveElt]...\n");
      return 0;
   }

   /* Check for limits option.  If present in position i (i as above) give
      limits and return. */
   if ( strcmp(argv[1], "-l") == 0 || strcmp(argv[1], "-L") == 0 ) {
      showLimits();
      return 0;
   }

   /* Check for verify option.  If present in position i (i as above) perform
      verify (Note verifyOptions terminates program). */
   if ( strcmp(argv[1], "-v") == 0 || strcmp(argv[1], "-V") == 0 ) 
      verifyOptions();

   /* Check for at least two parameters following options. */
   for ( optionCountPlus1 = 1 ; optionCountPlus1 <= argc-1 &&
              argv[optionCountPlus1][0] == '-' ; ++optionCountPlus1 )
      ;

   if ( argc - optionCountPlus1 < 2 ) {
      printf( "\n\nError: At least 2 non-option parameters are required.\n");
      exit(ERROR_RETURN_CODE);
   }

   /* Process options. */
   options.maxBaseSize = DEFAULT_MAX_BASE_SIZE;
   orderOption = FALSE;
   seed = 47;
   maxAttemptCount = 200;
   strcpy( options.outputFileMode, "w");
   for ( i = 1 ; i < optionCountPlus1 ; ++i )
      if ( strcmp( argv[i], "-a") == 0 )
         strcpy( options.outputFileMode, "a");
      else if ( strcmp( argv[i], "-f") == 0 )
         fixedPointsOption = TRUE;
      else if ( strcmp( argv[i], "-po") == 0 )
         orderOption = TRUE;
      else if ( strcmp( argv[i], "-i") == 0 )
         imageFormatFlag = TRUE;
      else if ( strncmp( argv[i], "-mb:", 4) == 0 ) {
         errno = 0;
         options.maxBaseSize = (Unsigned) strtol(argv[i]+4,NULL,0);
         if ( errno )
            ERROR( "main (cent)", "Invalid syntax for -mb option")
      }
      else if ( strncmp( argv[i], "-mw:", 4) == 0 ) {
         errno = 0;
         options.maxWordLength = (Unsigned) strtol(argv[i]+4,NULL,0);
         if ( errno )
            ERROR( "main (cent)", "Invalid syntax for -mw option")
      }
      else if ( strncmp(argv[i],"-m:",3) == 0 ) {
         errno = 0;
         maxAttemptCount = (unsigned long) strtol( argv[i]+3, NULL, 0);
         if ( errno )
            ERROR1s( "main (fndelt command)", "Invalid option ", argv[i], ".")
      }
      else if ( strncmp(argv[i],"-n:",3) == 0 )
         strcpy( outputObjectName, argv[i]+3);
      else if ( strncmp(argv[i],"-o:",3) == 0 ) {
         errno = 0;
         orderToFind = (unsigned long) strtol( argv[i]+3, NULL, 0);
         if ( errno )
            ERROR1s( "main (fndelt command)", "Invalid option ", argv[i], ".")
      }
      else if ( strncmp( argv[i], "-p:", 3) == 0 ) {
         strcpy( prefix, argv[i]+3);
      }
      else if ( strncmp( argv[i], "-t:", 3) == 0 ) {
         strcpy( suffix, argv[i]+3);
      }
      else if ( strncmp(argv[i],"-s:",3) == 0 ) {
         errno = 0;
         seed = (unsigned long) strtol( argv[i]+3, NULL, 0);
         if ( errno )
            ERROR1s( "main (fndelt command)", "Invalid option ", argv[i], ".")
      }
      else if ( strncmp(argv[i],"-wp:",4) == 0 )
         strcpy( permOutputName, argv[i]+4);
      else if ( strncmp(argv[i],"-wg:",4) == 0 )
         strcpy( groupOutputName, argv[i]+4);
      else
            ERROR1s( "main (fndelt command)", "Invalid option ", argv[i], ".")

   /* Compute maximum degree and word length. */
   options.maxWordLength = 200 + 5 * options.maxBaseSize;
   options.maxDegree = MAX_INT - 2 - options.maxBaseSize;

   /* Obtain number of involutions to find. */
   errno = 0;
   numberOfInvolsToFind = strtol( argv[optionCountPlus1+1], NULL, 0);
   if ( errno || numberOfInvolsToFind > 99 )
      ERROR1s( "main (fndinvol command)", "Invalid count ",
               argv[optionCountPlus1+1], ".");

   /* Compute file and library names. */
   parseLibraryName( argv[optionCountPlus1], prefix, suffix,
                     permGroupFileName, permGroupLibraryName);
   if ( *permOutputName )
      parseLibraryName( permOutputName, "", "",
                        permOutputFileName, permOutputLibraryName);
   if ( *groupOutputName )
      parseLibraryName( groupOutputName, "", "",
                           groupOutputFileName, groupOutputLibraryName);

   /* Read in group. */
   G = readPermGroup( permGroupFileName, permGroupLibraryName, 0, "Generate");

   /* Repeatedly generate random group elements.  When possible, take power
      to give desired order. */
   successCount = 0;
   attemptCount = 0;
   initializeSeed( seed);
   while ( successCount < numberOfInvolsToFind && ++attemptCount <= maxAttemptCount) {
      newPerm = randGroupPerm( G, 1);
      order = permOrder( newPerm);
      if ( (order = permOrder(newPerm)) % orderToFind == 0 ) {
         raisePermToPower( newPerm, order / orderToFind);
         newPerm->name[0] = 'x';
         invol[++successCount] = newPerm;
         sprintf( newPerm->name+1, "%d", successCount);
      }
   }

   /* Find the number of fixed points, if desired. */
   if ( fixedPointsOption ) {
      printf( "\n\n Number of fixed points.\n\n");
      for ( i = 1 ; i <= successCount ; ++i ) {
         f = 0;
         for ( j = 1 ; j <= G->degree ; ++j )
            f += (invol[i]->image[j] == j);
         printf( " %-5s %5d\n", invol[i]->name, f);
      }
   }

   /* Find orders of products, if desired. */
   if ( orderOption ) {
      printf( "\n\n Orders of products.\n");
      prodPerm = newUndefinedPerm( G->degree);
      for ( i = 1 ; i < successCount ; ++i )
         for ( j = i+1 ; j <= successCount ; ++j ) {
            copyPermutation( invol[i], prodPerm);
            rightMultiply( prodPerm, invol[j]);
            printf( "\n %-5s %-5s %8ld", invol[i]->name, invol[j]->name,
                                            permOrder( prodPerm) );
         }
   }

   /* Print involutions if requested, and write out group. */
   if ( groupOutputName[0] ) {
      involSubgroup = newTrivialPermGroup( G->degree);
      if ( outputObjectName[0] )
         strcpy( involSubgroup->name, outputObjectName);
      else
         strcpy( involSubgroup->name, groupOutputLibraryName);
      involSubgroup->base = NULL;
      involSubgroup->order = NULL;
      involSubgroup->printFormat = (imageFormatFlag ? imageFormat : cycleFormat);
      sprintf( comment, "Constructed by fndElt. Generators have order %d.",
               orderToFind);
      for ( j = optionCountPlus1+2 ; j < argc ; ++j ) {
         i = strtol(argv[j], NULL, 0);
         if ( i > successCount ) {
            printf( "\nFewer than %u permutations were found.\n", i);
            continue;
         }
         strcpy( invol[i]->name, "x");
         sprintf( invol[i]->name+1, "%d", i);
         invol[i]->next = NULL;
         if ( involSubgroup->generator )
            invol[i]->next = involSubgroup->generator;
         involSubgroup->generator = invol[i];
      }
      writePermGroup( groupOutputFileName, groupOutputLibraryName,
                     involSubgroup, comment);
   }

   if ( permOutputName[0] && optionCountPlus1+2 < argc ) {
      i = strtol(argv[optionCountPlus1+2], NULL, 0);
      if ( i < successCount ) {
         sprintf( comment, "Constructed by fndElt. Seed %lu, permutation %d.",
                  seed, i);
         if ( outputObjectName[0] )
            strcpy( invol[i]->name, outputObjectName);
         else
            strcpy( invol[i]->name, permOutputLibraryName);
         writePermutation( permOutputFileName, permOutputLibraryName,
                 invol[i], (imageFormatFlag ? "image" : "cycle"), comment);
      }
      else
         printf( "\nFewer than %u permutations were found.\n", i);
   }

   /* Terminate. */
   return 0;
}


/*-------------------------- verifyOptions -------------------------------*/

static void verifyOptions(void)
{
   CompileOptions mainOpts = { DEFAULT_MAX_BASE_SIZE, MAX_NAME_LENGTH,
                               MAX_PRIME_FACTORS,
                               MAX_REFINEMENT_PARMS, MAX_FAMILY_PARMS,
                               MAX_EXTRA,  XLARGE, SGND, NFLT};
   extern void xaddsge( CompileOptions *cOpts);
   extern void xbitman( CompileOptions *cOpts);
   extern void xcopy  ( CompileOptions *cOpts);
   extern void xcstbor( CompileOptions *cOpts);
   extern void xerrmes( CompileOptions *cOpts);
   extern void xessent( CompileOptions *cOpts);
   extern void xfactor( CompileOptions *cOpts);
   extern void xnew   ( CompileOptions *cOpts);
   extern void xoldcop( CompileOptions *cOpts);
   extern void xpermgr( CompileOptions *cOpts);
   extern void xpermut( CompileOptions *cOpts);
   extern void xprimes( CompileOptions *cOpts);
   extern void xrandgr( CompileOptions *cOpts);
   extern void xrandsc( CompileOptions *cOpts);
   extern void xreadgr( CompileOptions *cOpts);
   extern void xreadpe( CompileOptions *cOpts);
   extern void xstorag( CompileOptions *cOpts);
   extern void xtoken ( CompileOptions *cOpts);
   extern void xutil  ( CompileOptions *cOpts);

   xaddsge( &mainOpts);
   xbitman( &mainOpts);
   xcopy  ( &mainOpts);
   xcstbor( &mainOpts);
   xerrmes( &mainOpts);
   xessent( &mainOpts);
   xfactor( &mainOpts);
   xnew   ( &mainOpts);
   xoldcop( &mainOpts);
   xpermgr( &mainOpts);
   xpermut( &mainOpts);
   xprimes( &mainOpts);
   xrandgr( &mainOpts);
   xrandsc( &mainOpts);
   xreadgr( &mainOpts);
   xreadpe( &mainOpts);
   xstorag( &mainOpts);
   xtoken ( &mainOpts);
   xutil  ( &mainOpts);
}