Quelle soluble_orbits.c Sprache: C

/****************************************************************************
**
*A  soluble_orbits.c            ANUPQ source                   Eamonn O'Brien
**
*Y  Copyright 1995-2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
*Y  Copyright 1995-2001,  School of Mathematical Sciences, ANU,     Australia
**
*/

#include "pq_defs.h"
#include "pcp_vars.h"
#include "pga_vars.h"
#include "constants.h"
#include "pq_functions.h"

/* compute the orbits of the allowable subgroups,
   where the permutation group is soluble */

void
compute_orbits(int **a, int **b, char **c, int **perms, struct pga_vars *pga)
{
   register int alpha;
   int perm_number;

   /* set up space for orbit and stabiliser information */
   space_for_orbits(a, b, c, pga);

   /* now compute the orbits */

   for (alpha = 1; alpha <= pga->m; ++alpha) {
      if ((perm_number = pga->map[alpha]) != 0)
         orbits(perms[perm_number], *a, *b, *c, pga);
      else
         process_identity_perm(*a, *b, *c, pga);
   }
}

/* allocate and initialise space for orbit and stabiliser calculations */

void space_for_orbits(int **a, int **b, char **c, struct pga_vars *pga)
{
   register int i;
   register int Degree = pga->Degree;

   *a = allocate_vector(Degree, 1, FALSE);

   *b = allocate_vector(Degree, 1, TRUE);

   *c = allocate_char_vector(Degree, 1, FALSE);

   for (i = 1; i <= Degree; ++i) {
      *(*a + i) = i;
      *(*c + i) = 1;
   }
}

/* process identity permutation -- we need only to update c[j] which is the
   number of times j has been last image in orbit with leading term a[j] */

void process_identity_perm(int *a, int *b, char *c, struct pga_vars *pga)
{
   register int Degree = pga->Degree;
   int j, last, element;

   /* find the last entry, last, for each orbit, and increment c[last] */
   for (j = 1; j <= Degree; ++j) {
      if (a[j] == j) {
         /* trace this orbit */
         last = j;
         element = j;
         while (element != 0) {
            last = element;
            element = b[element];
         }
         ++c[last];
      }
   }
}

/* trace the action of the supplied permutation
   on the existing orbits where

   a[j] = leading term of existing orbit containing j
   b[j] = next term in existing orbit containing j

   c[j] = number of times j has been last image in orbit
          with leading term a[j] */

void orbits(int *permutation, int *a, int *b, char *c, struct pga_vars *pga)
{

   register int j;

   for (j = 1; j <= pga->Degree; ++j)
      if (a[j] == j)
         trace_action(permutation, j, a, b, c);
}

/* trace the action of the permutation on the orbit whose leading term is j */

void trace_action(int *permutation, int j, int *a, int *b, char *c)
{
   register int k, lead, image;
   Logical merge;

   /* find the last term, k, in the orbit of j */
   k = j;
   while (b[k] != 0)
      k = b[k];

   /* while the image of k lies outside the orbit whose leading term is j,
      merge the existing orbit of k with that of j by running through
      each element of the existing orbit of k and updating its entry
      in array a so that it now lies in the orbit with leading term j;
      let k be the last entry of the existing orbit */

   merge = TRUE;
   while (merge) {
      image = permutation[k];
      lead = a[image];
      if (lead != j) {
         b[k] = lead;
         while (b[k] != 0) {
            a[b[k]] = j;
            c[b[k]] = 0;
            k = b[k];
         }
      } else {
         ++c[k];
         merge = FALSE;
      }
   }
}

/* list the orbit with leading term j and return its length */

int soluble_list_orbit(int j, int *b, struct pga_vars *pga)
{
   register int orbit_length = 0;

   while (j != 0) {
      ++orbit_length;
      if (pga->print_orbits)
         printf("%d ", j);
      j = b[j];
   }

   return orbit_length;
}

/* find the orbit representatives, number of orbits, and orbit lengths;
   also list the individual orbits */

int *soluble_find_orbit_reps(int *a, int *b, struct pga_vars *pga)
{
   register int j;
   register int counter = 0;
   int *orbit_length;

   /* find the number of orbits */
   pga->nmr_orbits = 0;
   for (j = 1; j <= pga->Degree; ++j)
      if (a[j] == j)
         ++pga->nmr_orbits;

   /* set up space to store orbit representatives and orbit lengths */
   pga->rep = allocate_vector(pga->nmr_orbits, 1, 0);
   orbit_length = allocate_vector(pga->nmr_orbits, 1, 0);

   /* list the elements of each orbit and find its length */
   for (j = 1; j <= pga->Degree && counter <= pga->nmr_orbits; ++j) {
      if (a[j] == j) {
         ++counter;
         pga->rep[counter] = j;
         if (pga->print_orbits)
            printf("\nOrbit %d:\n", counter);
         orbit_length[counter] = soluble_list_orbit(j, b, pga);
         if (pga->print_orbits)
            printf("\nLength is %d\n", orbit_length[counter]);
      }
   }

   return orbit_length;
}

/* print out contents of three arrays created during orbit calculation */

void print_orbit_information(int *a, int *b, char *c, struct pga_vars *pga)
{
   printf("The array A is \n");
   print_array(a, 1, pga->nmr_subgroups + 1);

   printf("The array B is \n");
   print_array(b, 1, pga->nmr_subgroups + 1);

   printf("The array C is \n");
   print_chars(c, 1, pga->nmr_subgroups + 1);
}

quality94%

¤ Dauer der Verarbeitung: 0.12 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.