Quelle  graveyard.g   Sprache: unbekannt

# Here lies some old code and presumably rests in peace...

# from .gd:

#########################
# Stabilizer Iterators: #
#########################

#
# For stabilizers Stab_{U_i}(q) for an U_i-minimal q in P_i the following
# data structure can be used to iterate through the stabilizer:
#
#  stab is a component object with the following components:
#
BindGlobal( "StabIteratorsFamily", NewFamily( "StabIteratorsFamily" ) );
DeclareCategory( "IsStabIterator", IsComponentObjectRep );
DeclareRepresentation( "IsStdStabIteratorRep", IsStabIterator,
  [ "i",     # number of the subgroup in question
    "info",  # a list of length i, at position j we have a list of elements
             # in the transversal of U_{j-1} in U_j. These elements are stored
             # as numbers indexing words in setup.trans[j].
    "pos",   # a list of length i, at position j there is a number indexing
             # an element in info[j]. This is set to all 1 when Reset
             # is called and is incremented after a call to Next
    "cache", # intermediate results to reuse, a list of length i (as above,
             # height of stabilizer, each element is again a list of length
             # k+1 (for each representation), each element 
             # in there is an intermediate result)
    "point", # list of starting points to verify whether cache is valid
  ] );
BindGlobal( "StdStabIteratorsType", 
  NewType( StabIteratorsFamily, IsStabIterator and IsStdStabIteratorRep ) );
DeclareOperation( "StabIterator", [] );   # the constructor
DeclareOperation( "Reset", [ IsStabIterator ] );
DeclareOperation( "Next", [ IsStabIterator ] );
DeclareOperation( "Next", [ IsStabIterator, IsString ] );
DeclareGlobalFunction( "ORB_ApplyStabElement" );

DeclareGlobalFunction( "ORB_Minimalize2" );

DeclareGlobalFunction( "ORB_NextStabIterator2" );
DeclareGlobalFunction( "ORB_ApplyUElement" );

DeclareGlobalFunction( "OrbitBySuborbitWithKnownSize" );


# from .gi:

InstallGlobalFunction( ORB_Minimalize,
function(p,j,i,setup,stab,w)
  # p is a point that should be minimalized. j is in 1..k+1 and indicates,
  # whether p is in P_j or in P (for j=k+1). i is in 1..k and indicates, 
  # which group U_i is used to minimalize. So only i <= j makes sense.
  # setup is a record describing the helper subgroups as defined above. 
  # Returns a U_i-minimal point q in the same U_i-orbit pU_i.
  # If stab is "false" nothing happens. If stab is a stabiterator object,
  # (usually will be "newly born" thus empty), that will
  # be filled with information for an iterator object for 
  # Stab_{U_i}(pi[j][i](q)) (see above).
  # If w is a list the word which is applied is appended.
  local m,minpoint,minstab,minstablen,minword,n,oldp,q,qq,qqq,ret,stablen,
        tempstab,v,vv,vvv,ww,www;
#Print("Mini:",j," ",i,"\n");
  oldp := p;  # to make debugging easier!
  if i = 1 then    # this is the smallest helper subgroup

    # go to P_1:
    if j > i then 
      q := setup!.pifunc[j][i](p,setup!.pi[j][i]); 
    else
      q := p;
    fi;
    v := ValueHT(setup!.info[i],q);
    if v = fail then    # we do not yet know this point
      ###Print("<\c");
      # we have to enumerate this U_1-orbit, apply all elements in trans:
      v := [];  # here we collect the stabilizer
      for m in [1..setup!.index[i]] do
        qq := ORB_ApplyWord(q,ORB_InvWord(setup!.trans[i][m]),
                        setup!.els[i],setup!.elsinv[i],setup!.op[i]);
        if q = qq then   # we found a stabilizer element:
          Add(v,m);
        else
          vv := ValueHT(setup!.info[i],qq);
          if vv = fail then    # we did not yet reach this point
            AddHT(setup!.info[i],qq,m);   # store this info
          fi;
        fi;
      od;
      AddHT(setup!.info[i],q,v);
      setup!.suborbnr[i] := setup!.suborbnr[i] + 1;
      setup!.sumstabl[i] := setup!.sumstabl[i] + Length(v);
      ###Print(Length(v),":",QuoInt(setup!.sumstabl[i],
      ###      setup!.suborbnr[i]),">   \r");

      # now p is by definition U_1-minimal
    else    # we already know this U_1-orbit:
      if IsInt(v) then   # this is the number of a word
        if IsList(w) then Append(w,setup!.trans[i][v]); fi;  # store what we do
        p := ORB_ApplyWord(p,setup!.trans[i][v],setup!.els[j],
                           setup!.elsinv[j],setup!.op[j]);
        if j > i then
          q := setup!.pifunc[j][i](p,setup!.pi[j][i]);
        else
          q := p;
        fi;
        v := ValueHT(setup!.info[i],q);
      fi; # otherwise we are already U_1-minimal:
    fi;
    if IsStabIterator(stab) then
        stab!.i := 1;
        stab!.info := [v];
        stab!.pos := [1];
    fi;
#Print("Raus\n");
    return p;

  else   # we are in some higher helper subgroup than U_1:

    # first do a U_{i-1}-minimalization:
    p := ORB_Minimalize(p,j,i-1,setup,stab,w);

    # now try to reach the minimal U_{i-1}-suborbit in the U_i-orbit:
    if j > i then
      q := setup!.pifunc[j][i](p,setup!.pi[j][i]);
    else
      q := p;
    fi;
    v := ValueHT(setup!.info[i],q);

    if v = fail then    # we do not yet know this U_{i-1}-suborbit

      ###Print("<",i,":\c");
      # first we apply all elements of the transversal of U_{i-1} in U_i,
      # U_{i-1}-minimalize them and search for the smallest stabilizer
      # to choose the U_i-minimal U_{i-1}-orbit:
      minpoint := fail;
      minword := fail;
      minstablen := -1;
      minstab := fail;
      for m in [1..setup!.index[i]] do
        tempstab := StabIterator();
        qq := ORB_ApplyWord(q,setup!.trans[i][m],setup!.els[i],
                            setup!.elsinv[i],setup!.op[i]);
        ww := ShallowCopy(setup!.trans[i][m]);
        qq := ORB_Minimalize(qq,i,i-1,setup,tempstab,ww);
        stablen := Product(tempstab!.info,Length);
        if minpoint = fail or stablen < minstablen then
          minpoint := qq;
          minstablen := stablen;
          minword := ww;
          minstab := tempstab;
        fi;
      od;
      # Now U_i-minimalize p:
      p := ORB_ApplyWord(p,minword,setup!.els[j],setup!.elsinv[j],setup!.op[j]);
      if IsList(w) then Append(w,minword); fi;
      q := minpoint;
      # in the second component we have to collect stabilizing transversal 
      # elements for subgroups U_1 to U_i:
      v := [true,List([1..i],x->[])];  
      AddHT(setup!.info[i],q,v);
                        
      # Now the U_{i-1}-orbit of the vector q is the U_i-minimal 
      # U_{i-1}-orbit and q is the U_i-minimal vector
      
      # first find all U_{i-1}-minimal elements in the U_i-minimal 
      # U_{i-1}-orbit:
      Reset(minstab);
      repeat
        ww := [];
        qq := ORB_ApplyStabElement(q,i,i-1,setup,minstab,ww);
        if qq <> q then   # some new U_{i-1}-minimal element?
          vv := ValueHT(setup!.info[i],qq);
          if vv = fail then
            AddHT(setup!.info[i],qq,[false,ORB_InvWord(ww)]);
          fi;
        else   # in this case this is an element of Stab_{U_{i-1}}(q) in P_i
          for n in [1..i-1] do
            AddSet(v[2][n],minstab!.info[n][minstab!.pos[n]]);
          od;
        fi;
      until Next(minstab);
      
      # we have to enumerate this U_i-orbit by U_{i-1}-orbits, storing
      # information for all U_{i-1}-minimal vectors:
      tempstab := StabIterator();
      for m in [1..setup!.index[i]] do
        # Apply t to find other U_{i-1}-orbits
        qq := ORB_ApplyWord(q,setup!.trans[i][m],setup!.els[i],
                            setup!.elsinv[i],setup!.op[i]);
        ww := ShallowCopy(setup!.trans[i][m]);
        qq := ORB_Minimalize(qq,i,i-1,setup,tempstab,ww);
        vv := ValueHT(setup!.info[i],qq);
        if vv <> fail and not(IsInt(vv)) then  
          # we are again in the U_i-minimal U_{i-1}-o.
          # then m has to go in the stabilizer info:
          Add(v[2][i],m);
        fi;
        if vv = fail then   # a new U_{i-1}-orbit
          # note that we now have stabilizer info in tempstab
          ret := setup!.cosetrecog[i](i,ORB_InvWord(ww),setup);
          AddHT(setup!.info[i],qq,ret);
          Reset(tempstab);
          repeat
            www := ShallowCopy(ww);
            qqq := ORB_ApplyStabElement(qq,i,i-1,setup,tempstab,www);
            vvv := ValueHT(setup!.info[i],qqq);
            if vvv = fail then
              ret := setup!.cosetrecog[i](i,ORB_InvWord(www),setup);
              AddHT(setup!.info[i],qqq,ret);
            fi;
          until Next(tempstab);
        fi;
      od;
      # now q is by definition the U_i-minimal point in the orbit and
      # v its setup!.info[i], i.e. [true,stabilizer information]
      setup!.suborbnr[i] := setup!.suborbnr[i] + 1;
      setup!.sumstabl[i] := setup!.sumstabl[i] + Product(v[2],Length);
      ###Print(Product(v[2],Length),":",
      ###      QuoInt(setup!.sumstabl[i],setup!.suborbnr[i]),">      \r");

    else   # we already knew this U_{i-1}-suborbit

      if IsInt(v) then    # this is the number of a word
        if IsList(w) then 
          Append(w,setup!.trans[i][v]);   # remember what we did
        fi; 
        p := ORB_ApplyWord(p,setup!.trans[i][v],setup!.els[j],
                           setup!.elsinv[j],setup!.op[j]);
        # we again do a U_{i-1}-minimalization:
        p := ORB_Minimalize(p,j,i-1,setup,stab,w);
        # now we are in the U_i-minimal U_{i-1}-suborbit and on a 
        # U_{i-1}-minimal element
        if j > i then
          q := setup!.pifunc[j][i](p,setup!.pi[j][i]);
        else
          q := p;
        fi;
        v := ValueHT(setup!.info[i],q);
      fi;
      if v[1] = false then    # not yet U_i-minimal 
        # we still have to apply an element of Stab_{U_{i-1}}(pi[j][i-1](p)):
        if IsList(w) then Append(w,v[2]); fi;  # remember what we did
        p := ORB_ApplyWord(p,v[2],setup!.els[j],setup!.elsinv[j],setup!.op[j]);
        if j > i then
          q := setup!.pifunc[j][i](p,setup!.pi[j][i]);
        else
          q := p;
        fi;
        v := ValueHT(setup!.info[i],q);
      fi;
      # now q is the U_i-minimal element in qU_i
      # v is now [true,stabilizer information]

    fi;

    if IsStabIterator(stab) then
        stab!.i := i;
        stab!.info := v[2];
        stab!.pos := List([1..i],x->1);
    fi;

    # now we are on the minimal element in the S-orbit
#Print("raus\n");
    return p;
  fi;
end );

InstallGlobalFunction( OrbitBySuborbit,
function(p,hashlen,size,setup,percentage)
  # Enumerates the orbit of p under the group G generated by "gens" by
  # suborbits for the subgroup U described in "setup". 
  # "p" is a point
  # "hashlen" is an upper bound for the set of U-minimal points in the G-orbit
  # "size" is the group order to stop when we are ready and as upper bound
  #        for the orbit length
  # "setup" is a setup object for the iterated quotient trick,
  #         effectively enabling us to do minimalization with a subgroup
  # "percentage" is a number between 50 and 100 and gives a stopping criterium.
  #         We stop if percentage of the orbit is enumerated.
  #         Only over 50% we know that the stabilizer is correct!
  # Returns a suborbit database with additional field "words" which is
  # a list of words in gens which can be used to reach U-orbit in the G-orbit

  local k,firstgen,lastgen,stab,miniwords,db,stabgens,stabperms,stabilizer,
        fullstabsize,words,todo,i,j,x,mw,done,newperm,newword,oldtodo,sw,xx,v,
        pleaseexitnow,assumestabcomplete;

  pleaseexitnow := false;  # set this to true in a break loop to
                           # let this function exit gracefully
  assumestabcomplete := false;  # set this to true in a break loop to
                                # let this function assume that the 
                                # stabilizer is complete

  # Setup some shortcuts:
  k := setup!.k;
  firstgen := Length(setup!.els[k])+1;
  lastgen := Length(setup!.els[k+1]);

  # A security check:
  if p <> setup!.op[k+1](p,setup!.els[k+1][1]^0) then
      Error("Warning: The identity does not preserve the starting point!\n",
            "Did you normalize your vector?");
  fi;

  # First we U-minimalize p:
  stab := StabIterator();
  p := ORB_Minimalize(p,k+1,k,setup,stab,false);

  miniwords := [[]];  # here we collect U-minimalizing elements
  
  # Start a database with the first U-suborbit:
  db := SuborbitDatabase(setup,hashlen);
  StoreSuborbit(db,p,stab);

  stabgens := [];
  stabperms := [];
  stabilizer := Group(setup!.permgens[1]^0);
  if IsBound( setup!.stabchainrandom ) and setup!.stabchainrandom <> false then
      StabChain( stabilizer, rec( random := setup!.stabchainrandom ) );
  else
      StabChain(stabilizer);
  fi;
  fullstabsize := 1;
  
  words := [[]];
  todo := [[]];
  while true do

    i := 1;
    while i <= Length(todo) do
      if pleaseexitnow = true then return "didnotfinish"; fi;

      for j in [firstgen..lastgen] do
        x := setup!.op[k+1](p,setup!.els[k+1][j]);
        x := ORB_ApplyWord(x,todo[i],setup!.els[k+1],
                           setup!.elsinv[k+1],setup!.op[k+1]);
        mw := [];
        x := ORB_Minimalize(x,k+1,k,setup,stab,mw);
        v := LookupSuborbit(x,db);
        if v = fail then
          Add(words,Concatenation([j],todo[i]));
          Add(todo,Concatenation([j],todo[i]));
          Add(miniwords,mw);
          StoreSuborbit(db,x,stab);
          Print("t:",ORB_PrettyStringBigNumber(TotalLength(db)),
                " st:",ORB_PrettyStringBigNumber(fullstabsize),"       \r");
          if 2 * TotalLength(db) * fullstabsize > size and
             TotalLength(db) * fullstabsize * 100 >= size*percentage then 
            Print("\nDone!\n");
            return Objectify( StdOrbitBySuborbitsType,
                       rec(db := db,
                       words := words,
                       stabsize := fullstabsize,
                       stab := stabilizer,
                       stabwords := stabgens,
                       groupsize := size,
                       orbitlength := size/fullstabsize,
                       percentage := percentage,
                       seed := p ) );
          fi;
        else
          if assumestabcomplete = false and
             TotalLength(db) * fullstabsize * 2 <= size then
            # otherwise we know that we will not find more stabilizing els.
            # we know now that v is an integer and that
            # p*setup!.els[j]*todo[i]*U = p*words[v]*U
            # p*setup!.els[j]*todo[i]*mw is our new vector
            # p*words[v]*miniwords[v] is our old vector
            # they differ by an element in Stab_U(...)
            Reset(stab);
            done := false;
            repeat
              sw := [];
              xx := ORB_ApplyStabElement(x,k+1,k,setup,stab,sw);
              if xx = Representatives(db)[v] then  
                # we got a real stabilizer element of p
                done := true;
                newword := Concatenation([j],todo[i],mw,sw,
                            ORB_InvWord(miniwords[v]),ORB_InvWord(words[v]));
                newperm := ORB_ApplyWord(setup!.permgens[1]^0,newword,
                                 setup!.permgens,setup!.permgensinv,OnRight);
                if not(IsOne(newperm)) then
                  if not(newperm in stabilizer) then
                    Add(stabgens,newword);
                    Add(stabperms,newperm);
                    stabilizer := GroupWithGenerators(stabperms);
                    Print("\nCalculating new estimate of the stabilizer...\c");
                    if IsBound(setup!.stabchainrandom) and 
                       setup!.stabchainrandom <> false then
                        StabChain(stabilizer, 
                                  rec(random := setup!.stabchainrandom));
                    else
                        StabChain(stabilizer);
                    fi;
                    fullstabsize := Size(stabilizer);
                    Print("done.\nNew stabilizer order: ",fullstabsize,"\n");
                    if TotalLength(db) * fullstabsize * 100
                       >= size*percentage then 
                      Print("Done!\n");
                      return Objectify( StdOrbitBySuborbitsType,
                             rec(db := db,
                                 words := words,
                                 stabsize := fullstabsize,
                                 stab := stabilizer,
                                 stabwords := stabgens,
                                 groupsize := size,
                                 orbitlength := size/fullstabsize,
                                 percentage := percentage,
                                 seed := p) );
                    fi;
                  fi;
                fi;
              fi;
            until done or Next(stab);
          fi;
        fi;
      od;
      i := i + 1;
    od;
  
    oldtodo := todo;
    todo := [];
    for i in [1..Length(stabgens)] do
      Append(todo,List(oldtodo,w->Concatenation(stabgens[i],w)));
    od;
    Print("\nLength of next todo: ",Length(todo),"\n");
  od;
  # this is never reached
end );

InstallGlobalFunction( OrbitBySuborbitWithKnownSize,
function(p,hashlen,size,setup,randels)
  # Enumerates the orbit of p under the group G generated by "gens" by
  # suborbits for the subgroup U described in "setup". 
  #   "p" is a point
  #   "hashlen" is an upper bound for the set of U-minimal points in the G-orbit
  #   "size" is the orbit length
  #   "setup" is a record of data for the iterated quotient trick,
  #           effectively enabling us to do minimalization with a subgroup
  #   "randels" number of random elements to use for recognising half orbits
  # Returns a record with components:
  #   "db": suborbit database
  #   "words": a list of words in gens which can be used to reach 
  #            U-orbit in the G-orbit
  local k,stab,q,trans,db,l,i,Ucounter,g,j,x,y,v,ii,w,z,firstgen,lastgen;

  k := setup!.k;
  firstgen := Length(setup!.els[k])+1;
  lastgen := Length(setup!.els[k+1]);

  # First we U-minimalize p:
  stab := StabIterator();
  q := ORB_Minimalize(p,k+1,k,setup,stab,false);

  trans := [[]];    # words for getting to the U-suborbits
  
  # Start a database with the first U-suborbit:
  db := SuborbitDatabase(setup,hashlen);
  StoreSuborbit(db,q,stab);

  l := [p];
  i := 1;   # counts elements in l
  # use a stabilizer info, which describes all of U:
  Ucounter := StabIterator();
  Ucounter!.i := k;
  Ucounter!.info := List([1..k],i->[1..setup!.index[i]]);
  Ucounter!.pos := List([1..k],i->1);

  # Throw in some vectors gotten by applying random elements:
  g := GroupWithGenerators(setup!.els[k+1]{[firstgen..lastgen]});
  for j in [1..randels] do
      Print("Applying random element ",j," (",randels,") ...\n");
      x := p * PseudoRandom(g);
      y := ORB_Minimalize(x,k+1,k,setup,stab,false);
      v := LookupSuborbit(y,db);
      if v = fail then
          Add(l,x);
          Add(trans,[fail]);
          StoreSuborbit(db,y,stab);
          Print("total: ",ORB_PrettyStringBigNumber(TotalLength(db)),"     \n");
      fi;
      if TotalLength(db) >= size then 
        Print("\nDone.\n");
        return rec( db := db, words := trans ); 
      fi;
  od;
  Unbind(g);
   
  Reset(Ucounter);
  repeat
    while i <= Length(l) do
      for j in [firstgen..lastgen] do
        x := setup!.op[k+1](l[i],setup!.els[k+1][j]);
        y := ORB_Minimalize(x,k+1,k,setup,stab,false);
        v := LookupSuborbit(y,db);
        if v = fail then
          Add(trans,Concatenation(trans[i],[j]));
          Add(l,x);
          StoreSuborbit(db,y,stab);
          Print("total: ",ORB_PrettyStringBigNumber(TotalLength(db)),"     \r");
          if TotalLength(db) >= size then 
            Print("\nDone.\n");
            return rec( db := db, words := trans ); 
          fi;
        fi;
      od;
      i := i + 1;
    od;
    # now we have to to something else, perhaps applying some U elements?
    Print(".\c");
    for ii in [1..Length(l)] do
      w := [];
      z := ORB_ApplyUElement(l[ii],k+1,k,setup,Ucounter,w);
      for j in [firstgen..lastgen] do
        x := setup!.op[k+1](z,setup!.els[k+1][j]);
        y := ORB_Minimalize(x,k+1,k,setup,stab,false);
        v := LookupSuborbit(y,db);
        if v = fail then
          Add(trans,Concatenation(trans[ii],w,[j]));
          Add(l,x);
          StoreSuborbit(db,y,stab);
          Print("total: ",ORB_PrettyStringBigNumber(TotalLength(db)),"     \r");
          if TotalLength(db) >= size then 
            Print("\nDone.\n");
            return rec( db := db, words := trans ); 
          fi;
        fi;
      od;
    od;
  until Next(Ucounter,"fromabove");

  Print("Warning! Orbit not complete!!!\n");
  # this should never happen!
  return rec( db := db, words := trans );
end );

InstallGlobalFunction( OrbitBySuborbitBootstrapForVectors,
function(gens,permgens,sizes,codims)
  # Returns a setup object for a list of helper subgroups
  # gens: a list of lists of generators for U_1 < U_2 < ... < U_k < G
  # permgens: the same in a faithful permutation representation
  # sizes: a list of sizes of groups U_1 < U_2 < ... < U_k
  # codims: a list of dimensions of factor modules
  # note that the basis must be changed to make projection easy!
  # That is, projection is taking the components [1..codim].

  local dim,doConversions,f,i,j,k,nrgens,nrgenssum,o,regvec,sample,setup,sum,v,
        counter,merk,neededfullspace;

  # For the old compressed matrices:
  if IsGF2MatrixRep(gens[1][1]) or Is8BitMatrixRep(gens[1][1]) then
      doConversions := true;
  else
      doConversions := false;
  fi;

  # Some preparations:
  k := Length(sizes);
  if Length(gens) <> k+1 or Length(permgens) <> k+1 or Length(codims) <> k then
      Error("Need generators for ",k+1," groups and ",k," codimensions.");
      return;
  fi;
  nrgens := List(gens,Length);
  nrgenssum := 0*nrgens;
  sum := 0;
  for i in [1..k+1] do
      nrgenssum[i] := sum;
      sum := sum + nrgens[i];
  od;
  nrgenssum[k+2] := sum;

  sample := gens[1][1][1];  # first vector of first generator

  # Do the first step:
  setup := rec(k := 1);
  setup.size := [sizes[1]];
  setup.index := [sizes[1]];
  setup.permgens := Concatenation(permgens);
  setup.permgensinv := List(setup.permgens,x->x^-1);
  setup.els := [];
  setup.els[k+1] := Concatenation(gens);
  setup.elsinv := [];
  setup.elsinv[k+1] := List(setup.els[k+1],x->x^-1);
  setup.cosetinfo := [];
  setup.cosetrecog := [];
  setup.hashlen := List([1..k+1],i->100000);
  dim := Length(gens[1][1]);
  codims[k+1] := dim;   # for the sake of completeness!
  for j in [1..k] do
      setup.els[j] := List(Concatenation(gens{[1..j]}),
                           x->ExtractSubMatrix(x,[1..codims[j]],
                                                 [1..codims[j]]));
      if doConversions then
          for i in setup.els[j] do ConvertToMatrixRep(i); od;
      fi;
      setup.elsinv[j] := List(setup.els[j],x->x^-1);
  od;
  f := BaseField(gens[1][1]);
  regvec := ZeroVector(sample,codims[1]);  
            # a new empty vector over same field
  Info(InfoOrb,1,"Looking for regular U1-orbit in factor space...");
  counter := 0;
  repeat
      counter := counter + 1;
      Randomize(regvec);
      o := Enumerate(Orb(setup.els[1],regvec,OnRight,
                         rec(hashlen := sizes[1]*2, schreier := true)));
      Info(InfoOrb,2,"Found length: ",Length(o!.orbit));
  until Length(o!.orbit) = sizes[1] or counter >= 10;
  if Length(o!.orbit) < sizes[1] then   # Bad luck, try something else:
    regvec := ZeroMutable(sample);
    Info(InfoOrb,1,"Looking for regular U1-orbit in full space...");
    counter := 0;
    repeat
        counter := counter + 1;
        Randomize(regvec);
        o := Enumerate(Orb(gens[1],regvec,OnRight,
                           rec(hashlen := sizes[1]*2, schreier := true)));
        Info(InfoOrb,2,"Found length: ",Length(o!.orbit));
    until Length(o!.orbit) = sizes[1] or counter >= 10;
    if Length(o!.orbit) < sizes[1] then   # Again bad luck, try the regular rep
        Info(InfoOrb,1,"Using the regular permutation representation...");
        o := Enumerate(Orb(gens[1],gens[1]^0,OnRight,
                                 rec(hashlen := sizes[1]*2, schreier := true)));
    fi;
  fi;
  Info(InfoOrb,2,"Found!");
  setup.trans := [List([1..Length(o!.orbit)],i->TraceSchreierTreeForward(o,i))];

  # Note that for k=1 we set codims[2] := dim
  setup.pi := [];
  setup.pifunc := [];
  for j in [2..k+1] do
      setup.pi[j] := [];
      setup.pifunc[j] := [];
      for i in [1..j-1] do
          setup.pi[j][i] := [1..codims[i]];
          setup.pifunc[j][i] := \{\};
      od;
  od;
  setup.info := [NewHT(regvec,Size(f)^(codims[1]) * 3)];
  setup.suborbnr := [0];
  setup.sumstabl := [0];
  setup.regvecs := [regvec];
  setup.op := List([1..k+1],i->OnRight);
  setup.sample := [regvec,gens[1][1][1]];

  Objectify( NewType( OrbitBySuborbitSetupFamily,
                      IsOrbitBySuborbitSetup and IsStdOrbitBySuborbitSetupRep ),
             setup );
  # From now on we can use it and it is an object!

  neededfullspace := false;

  # Now do the other steps:
  for j in [2..k] do
      # First find a vector the orbit of which identifies the U_{j-1}-cosets
      # of U_j, i.e. Stab_{U_j}(v) <= U_{j-1}, 
      # we can use the j-1 infrastructure!
      if not(neededfullspace) then
        # if we have needed the full space somewhere, we need it everywhere
        # else, because OrbitBySuborbit is only usable for big vectors!
        Info(InfoOrb,1,"Looking for U",j-1,"-coset-recognising U",j,"-orbit ",
             "in factor space...");
        regvec := ZeroVector(sample,codims[j]);
        counter := 0;
        repeat
            Randomize(regvec);
            counter := counter + 1;
            # Now U_{j-1}-minimalize it, such that the transversal-words
            # returned reach the U_{j-1}-suborbits we find next:
            regvec := ORB_Minimalize(regvec,j,j-1,setup,false,false);
            o := OrbitBySuborbit(regvec,(sizes[j]/sizes[j-1])*2+1,sizes[j],
                                 setup,100);
            Info(InfoOrb,2,"Found ",Length(Representatives(o!.db)),
                 " suborbits (need ",sizes[j]/sizes[j-1],")");
        until Length(Representatives(o!.db)) = sizes[j]/sizes[j-1] or 
              counter >= 3;
      fi;
      if neededfullspace or
         Length(Representatives(o!.db)) < sizes[j]/sizes[j-1] then
        neededfullspace := true;
        # Bad luck, try the full space:
        Info(InfoOrb,1,"Looking for U",j-1,"-coset-recognising U",j,"-orbit ",
             "in full space...");
        regvec := ZeroMutable(sample);
        counter := 0;
        # Go to the original generators, using the infrastructure for k=j-1:
        merk := [setup!.els[j],setup!.elsinv[j]];
        setup!.els[j] := Concatenation(gens{[1..j]});
        setup!.elsinv[j] := List(setup!.els[j],x->x^-1);
        setup!.sample[j] := ShallowCopy(regvec);  # now a longer vector!
        # this is corrected later on!
        repeat
            Randomize(regvec);
            counter := counter + 1;
            # Now U_{j-1}-minimalize it, such that the transversal-words
            # returned reach the U_{j-1}-suborbits we find next:
            regvec := ORB_Minimalize(regvec,j,j-1,setup,false,false);
            o := OrbitBySuborbit(regvec,(sizes[j]/sizes[j-1])*2+1,sizes[j],
                                 setup,100);
            Info(InfoOrb,2,"Found ",Length(Representatives(o!.db)),
                 " suborbits (need ",sizes[j]/sizes[j-1],")");
        until Length(Representatives(o!.db)) = sizes[j]/sizes[j-1] or
              counter >= 20;
        if Length(Representatives(o!.db)) < sizes[j]/sizes[j-1] then
            Info(InfoOrb,1,"Bad luck, did not find nice orbit, giving up.");
            return;
        fi;
        setup!.els[j] := merk[1];
        setup!.elsinv[j] := merk[2];
      fi;

      Info(InfoOrb,1,"Found U",j-1,"-coset-recognising U",j,"-orbit!");
      setup!.k := j;
      setup!.size[j] := sizes[j];
      setup!.index[j] := sizes[j]/sizes[j-1];
      setup!.trans[j] := o!.words;
      setup!.suborbnr[j] := 0;
      setup!.sumstabl[j] := 0;
      setup!.info[j] :=
            NewHT(regvec,QuoInt(Size(f)^(codims[j]),sizes[j-1])*4+1); # fixme!
      setup!.regvecs[j] := regvec;
      if not(neededfullspace) then
          setup!.cosetrecog[j] := ORB_CosetRecogGenericFactorSpace;
          setup!.cosetinfo[j] := o!.db;   # the hash table
      else
          setup!.cosetrecog[j] := ORB_CosetRecogGenericFullSpace;
          setup!.cosetinfo[j] := [o!.db,k];   # the hash table
      fi;
      setup!.sample[j] := ZeroVector(sample,codims[j]);
      setup!.sample[j+1] := sample;
  od;
  return setup;
end );

InstallGlobalFunction( ORB_CosetRecogGenericFactorSpace,
  function( j, w, s )
    local x;
    x := ORB_ApplyWord(s!.regvecs[j],w,s!.els[j],s!.elsinv[j],s!.op[j]);
    x := ORB_Minimalize(x,j,j-1,s,false,false);
    return LookupSuborbit(x,s!.cosetinfo[j]);
  end );

InstallGlobalFunction( ORB_CosetRecogGenericFullSpace,
  function( j, w, s )
    local x,k;
    k := s!.cosetinfo[j][2];
    x := ORB_ApplyWord(s!.regvecs[j],w,s!.els[k+1],s!.elsinv[k+1],
                       s!.op[k+1]);
    x := ORB_Minimalize(x,k+1,j-1,s,false,false);
    return LookupSuborbit(x,s!.cosetinfo[j][1]);
  end );

InstallGlobalFunction( OrbitBySuborbitBootstrapForLines,
function(gens,permgens,sizes,codims)
  # Returns a setup object for a list of helper subgroups
  # gens: a list of lists of generators for U_1 < U_2 < ... < U_k < G
  # permgens: the same in a faithful permutation representation
  # sizes: a list of sizes of groups U_1 < U_2 < ... < U_k
  # codims: a list of dimensions of factor modules
  # note that the basis must be changed to make projection easy!
  # That is, projection is taking the components [1..codim].

  local dim,doConversions,f,i,j,k,nrgens,nrgenssum,o,regvec,sample,setup,sum,v,
        counter,merk,neededfullspace,c;

  # For the old compressed matrices:
  if IsGF2MatrixRep(gens[1][1]) or Is8BitMatrixRep(gens[1][1]) then
      doConversions := true;
  else
      doConversions := false;
  fi;

  # Some preparations:
  k := Length(sizes);
  if Length(gens) <> k+1 or Length(permgens) <> k+1 or Length(codims) <> k then
      Error("Need generators for ",k+1," groups and ",k," codimensions.");
      return;
  fi;
  nrgens := List(gens,Length);
  nrgenssum := 0*nrgens;
  sum := 0;
  for i in [1..k+1] do
      nrgenssum[i] := sum;
      sum := sum + nrgens[i];
  od;
  nrgenssum[k+2] := sum;

  sample := gens[1][1][1];  # first vector of first generator

  # Do the first step:
  setup := rec(k := 1);
  setup.size := [sizes[1]];
  setup.index := [sizes[1]];
  setup.permgens := Concatenation(permgens);
  setup.permgensinv := List(setup.permgens,x->x^-1);
  setup.els := [];
  setup.els[k+1] := Concatenation(gens);
  setup.elsinv := [];
  setup.elsinv[k+1] := List(setup.els[k+1],x->x^-1);
  setup.cosetinfo := [];
  setup.cosetrecog := [];
  setup.hashlen := List([1..k+1],i->1000000);
  dim := Length(gens[1][1]);
  codims[k+1] := dim;   # for the sake of completeness!
  for j in [1..k] do
      setup.els[j] := List(Concatenation(gens{[1..j]}),
                           x->ExtractSubMatrix(x,[1..codims[j]],
                                                 [1..codims[j]]));
      if doConversions then
          for i in setup.els[j] do ConvertToMatrixRep(i); od;
      fi;
      setup.elsinv[j] := List(setup.els[j],x->x^-1);
  od;
  f := BaseField(gens[1][1]);
  regvec := ZeroVector(sample,codims[1]);  
            # a new empty vector over same field
  Info(InfoOrb,1,"Looking for regular U1-orbit in factor space...");
  counter := 0;
  repeat
      counter := counter + 1;
      Randomize(regvec);
      c := PositionNonZero( regvec );
      if c <= Length( regvec )  then
          regvec := Inverse( regvec[c] ) * regvec;
      fi;
      o := Enumerate(Orb(setup.els[1],regvec,OnLines,
                         rec(hashlen := sizes[1]*2, schreier := true)));
      Info(InfoOrb,2,"Found length: ",Length(o!.orbit));
  until Length(o!.orbit) = sizes[1] or counter >= 10;
  if Length(o!.orbit) < sizes[1] then   # Bad luck, try something else:
    regvec := ZeroMutable(sample);
    Info(InfoOrb,1,"Looking for regular U1-orbit in full space...");
    counter := 0;
    repeat
        counter := counter + 1;
        Randomize(regvec);
        c := PositionNonZero( regvec );
        if c <= Length( regvec )  then
            regvec := Inverse( regvec[c] ) * regvec;
        fi;
        o := Enumerate(Orb(gens[1],regvec,OnLines,
                                 rec(hashlen := sizes[1]*2, schreier := true)));
        Info(InfoOrb,2,"Found length: ",Length(o!.orbit));
    until Length(o!.orbit) = sizes[1] or counter >= 10;
    if Length(o!.orbit) < sizes[1] then   # Again bad luck, try the regular rep
        Info(InfoOrb,1,"Using the permutation representation...");
        o := Enumerate(Orb(permgens[1],permgens[1]^0,OnRight,
                                 rec(hashlen := sizes[1]*2, schreier := true)));
    fi;
  fi;
  Info(InfoOrb,2,"Found!");
  setup.trans := [List([1..Length(o!.orbit)],i->TraceSchreierTreeForward(o,i))];

  # Note that for k=1 we set codims[2] := dim
  setup.pi := [];
  setup.pifunc := [];
  for j in [2..k+1] do
      setup.pi[j] := [];
      setup.pifunc[j] := [];
      for i in [1..j-1] do
          setup.pi[j][i] := [1..codims[i]];
          setup.pifunc[j][i] := \{\};
      od;
  od;
  setup.info := [NewHT(regvec,Size(f)^(codims[1]) * 3)];
  setup.suborbnr := [0];
  setup.sumstabl := [0];
  setup.regvecs := [regvec];
  setup.op := List([1..k+1],i->OnLines);
  setup.sample := [regvec,gens[1][1][1]];

  Objectify( NewType( OrbitBySuborbitSetupFamily,
                      IsOrbitBySuborbitSetup and IsStdOrbitBySuborbitSetupRep ),
             setup );
  # From now on we can use it and it is an object!

  neededfullspace := false;

  # Now do the other steps:
  for j in [2..k] do
      # First find a vector the orbit of which identifies the U_{j-1}-cosets
      # of U_j, i.e. Stab_{U_j}(v) <= U_{j-1}, 
      # we can use the j-1 infrastructure!
      if not(neededfullspace) then
        # if we have needed the full space somewhere, we need it everywhere
        # else, because OrbitBySuborbit is only usable for big vectors!
        Info(InfoOrb,1,"Looking for U",j-1,"-coset-recognising U",j,"-orbit ",
             "in factor space...");
        regvec := ZeroVector(sample,codims[j]);
        counter := 0;
        repeat
            Randomize(regvec);
            c := PositionNonZero( regvec );
            if c <= Length( regvec )  then
                regvec := Inverse( regvec[c] ) * regvec;
            fi;
            # Now U_{j-1}-minimalize it, such that the transversal-words
            # returned reach the U_{j-1}-suborbits we find next:
            regvec := ORB_Minimalize(regvec,j,j-1,setup,false,false);
            counter := counter + 1;
            o := OrbitBySuborbit(regvec,(sizes[j]/sizes[j-1])*2+1,sizes[j],
                                 setup,100);
            Info(InfoOrb,2,"Found ",Length(Representatives(o!.db)),
                 " suborbits (need ",sizes[j]/sizes[j-1],")");
        until Length(Representatives(o!.db)) = sizes[j]/sizes[j-1] or 
              counter >= 3;
      fi;
      if neededfullspace or
         Length(Representatives(o!.db)) < sizes[j]/sizes[j-1] then
        neededfullspace := true;
        # Bad luck, try the full space:
        Info(InfoOrb,1,"Looking for U",j-1,"-coset-recognising U",j,"-orbit ",
             "in full space...");
        regvec := ZeroMutable(sample);
        counter := 0;
        # Go to the original generators, using the infrastructure for k=j-1:
        merk := [setup!.els[j],setup!.elsinv[j]];
        setup!.els[j] := Concatenation(gens{[1..j]});
        setup!.elsinv[j] := List(setup!.els[j],x->x^-1);
        setup!.sample[j] := ShallowCopy(regvec);  # now a longer vector
        # this will be corrected later on
        repeat
            Randomize(regvec);
            c := PositionNonZero( regvec );
            if c <= Length( regvec )  then
                regvec := Inverse( regvec[c] ) * regvec;
            fi;
            # Now U_{j-1}-minimalize it, such that the transversal-words
            # returned reach the U_{j-1}-suborbits we find next:
            regvec := ORB_Minimalize(regvec,j,j-1,setup,false,false);
            counter := counter + 1;
            o := OrbitBySuborbit(regvec,(sizes[j]/sizes[j-1])*2+1,sizes[j],
                                 setup,100);
            Info(InfoOrb,2,"Found ",Length(Representatives(o!.db)),
                 " suborbits (need ",sizes[j]/sizes[j-1],")");
        until Length(Representatives(o!.db)) = sizes[j]/sizes[j-1] or
              counter >= 20;
        if Length(Representatives(o!.db)) < sizes[j]/sizes[j-1] then
            Info(InfoOrb,1,"Bad luck, did not find nice orbit, giving up.");
            return;
        fi;
        setup!.els[j] := merk[1];
        setup!.elsinv[j] := merk[2];
      fi;

      Info(InfoOrb,2,"Found U",j-1,"-coset-recognising U",j,"-orbit!");
      setup!.k := j;
      setup!.size[j] := sizes[j];
      setup!.index[j] := sizes[j]/sizes[j-1];
      setup!.trans[j] := o!.words;
      setup!.suborbnr[j] := 0;
      setup!.sumstabl[j] := 0;
      setup!.info[j] :=
            NewHT(regvec,QuoInt(Size(f)^(codims[j]),sizes[j-1])*4+1); # fixme!
      setup!.regvecs[j] := regvec;
      if not(neededfullspace) then
          setup!.cosetrecog[j] := ORB_CosetRecogGenericFactorSpace;
          setup!.cosetinfo[j] := o!.db;   # the hash table
      else
          setup!.cosetrecog[j] := ORB_CosetRecogGenericFullSpace;
          setup!.cosetinfo[j] := [o!.db,k];   # the hash table
      fi;
      setup!.sample[j] := ZeroVector(sample,codims[j]);
      setup!.sample[j+1] := sample;
  od;
  return setup;
end );

InstallGlobalFunction( IsVectorInOrbitBySuborbitList,
function(v,obsol)
  local i,j,k,res,s,x;
  s := obsol.setup;
  k := s!.k;
  for j in [1..obsol.nrrandels] do
      x := s!.op[k+1](v,obsol.randels[j]);
      x := ORB_Minimalize(x,k+1,k,s,false,false);
      for i in [1..Length(obsol.obsos)] do
          res := LookupSuborbit(x,obsol.obsos[i]!.db);
          if res <> fail then  # we know this N-orbit
              return i;  # is in orbit number i
          fi;
      od;
  od;
  return fail;
end );


InstallGlobalFunction( ORB_ApplyStabElement,
function(p,j,i,setup,stab,w)
  local ww,www;
  while true do
    if i > 1 and IsBound(stab!.point[i][j]) and p = stab!.point[i][j] then
      if IsList(w) then Append(w,stab!.cache[i][j][1]); fi;
      p := stab!.cache[i][j][2];
    else
      stab!.point[i][j] := p;

      ww := ShallowCopy(setup!.trans[i][stab!.info[i][stab!.pos[i]]]);
      if IsList(w) then Append(w,ww); fi;
      p := ORB_ApplyWord(p,ww,setup!.els[j],setup!.elsinv[j],setup!.op[j]);
      if i = 1 then
        return p;
      fi;
      www := [];
      p := ORB_Minimalize(p,j,i,setup,false,www);
      Append(ww,www);
      if IsList(w) then Append(w,www); fi;

      stab!.cache[i][j] := [ww,p];
    fi;
    i := i - 1;
  od;
  # never comes here
end );

InstallMethod( StoreSuborbit, 
  "for a suborbit database, a point, a stabiterator, and a setup object",
  [ IsSuborbitDatabase and IsStdSuborbitDbRep, IsObject, IsStabIterator ],
  function(db,p,stab)
  # "db" must be a suborbit database
  # "p" must be a U-minimal element, which is not yet known
  # "stab" must be stabilizer information coming from minimalization
  # all U-minimal elements in the same orbit are calculated and stored
  # in the hash, in addition "p" is appended as representative to
  # "suborbits" and the orbit length is calculated and appended to
  # "lengths".
  local setup, k, firstgen, lastgen, li, i, j, pp, vv, nrmins, length,stabsize;
        
  setup := db!.setup;
  k := setup!.k;
  Add(db!.reps,p);
  AddHT(db!.mins,p,Length(db!.reps));
  ###Print("[",Product(stab.info,Length),"\c");
  if Size(stab) = setup!.size[k] then
    # better use a standard orbit algorithm:
    if k = 1 then
      firstgen := 1;
    else
      firstgen := Length(setup!.els[k-1])+1;
    fi;
    lastgen := Length(setup!.els[k]);
    li := [p];
    i := 1;
    while i <= Length(li) do
      for j in [firstgen..lastgen] do
        pp := setup!.op[k+1](li[i],setup!.els[k+1][j]);  # ???
        vv := ValueHT(db!.mins,pp);
        if vv = fail then
          AddHT(db!.mins,pp,Length(db!.reps));
          Add(li,pp);
        fi;
      od;
      i := i + 1;
    od;
    nrmins := Length(li);
    length := nrmins;
  else
    Reset(stab);
    nrmins := 1;
    stabsize := 0;
    repeat
      pp := ORB_ApplyStabElement(p,k+1,k,setup,stab,false);
      if p = pp then  # we got a real stabilizer element of p
        stabsize := stabsize + 1;
      else  # we could have stepped to some other U-minimal element
        vv := ValueHT(db!.mins,pp);
        if vv = fail then
          AddHT(db!.mins,pp,Length(db!.reps));
          nrmins := nrmins+1;
        fi;
      fi;
    until Next(stab);
    length := setup!.size[k] / stabsize;
  fi;
  Add(db!.lengths,length);
  db!.totallength := db!.totallength + length;
  ###Print("]\r");
  Print("\r#",Length(db!.reps),
        ",S:",ORB_PrettyStringBigNumber(length),",\c");
  Print("M:",nrmins,"  \c");
  return length;
end );

InstallMethod( SuborbitDatabase, "for an orbit by suborbit setup object",
  [ IsOrbitBySuborbitSetup, IsPosInt ],
  function( setup, hashlen )
    # i is the number of subgroups used for the trick, i>=1
    local r;
    r := rec( reps := [], lengths := [], setup := setup, totallength := 0,
              i := setup!.k, j := setup!.k+1 );
    r.mins := NewHT( setup!.sample[setup!.k+1], hashlen );
    Objectify( StdSuborbitDatabasesType, r );
    return r;
  end );

#########################
# Stabilizer Iterators: #
#########################

InstallMethod( StabIterator, "without arguments", [],  
  function( )
    local stab;
    stab := rec();
    Objectify( StdStabIteratorsType, stab );
    return stab;
  end );

InstallMethod( ViewObj, "for a stab iterator", 
  [ IsStabIterator and IsStdStabIteratorRep ],
  function( stab )
    if not(IsBound(stab!.i)) then
        Print("<newly born stab iterator>");
    else
        Print("<stabiterator size=",stab!.info," position=",stab!.pos,">");
    fi;
  end );

InstallMethod( Reset, "for a stab iterator",
  [ IsStabIterator and IsStdStabIteratorRep ],
function(stab)
  if not(IsBound(stab!.i)) then
      Error("StabIterator is not yet initialized");
      return;
  fi;
  stab!.pos := List(stab!.info,x->1);
  stab!.point := List([1..stab!.i],x->[]);
  stab!.cache := List([1..stab!.i],x->[]);
end );

InstallOtherMethod( Size, "for a std stab iterator",
  [ IsStabIterator and IsStdStabIteratorRep ],
  function( stab )
    return Product( stab!.info, Length );
  end );

InstallMethod( Next, "for a stab iterator",
  [ IsStabIterator and IsStdStabIteratorRep ],
function(stab)
  local i;
  i := 1;
  while true do
    if i > Length(stab!.pos) then
      return true;   # finished with this iterator
    fi;
    stab!.pos[i] := stab!.pos[i]+1;
    stab!.point[i] := [];    # this is no longer valid
    if stab!.pos[i] <= Length(stab!.info[i]) then
      return false;  # next element found
    fi;
    stab!.pos[i] := 1;
    i := i + 1;
  od;
  # this is never reached
end );

InstallMethod( Next, "for a stab iterator and a string",
  [ IsStabIterator and IsStdStabIteratorRep, IsString ],
function(stab,st)
  local i;
  i := stab!.i;
  while true do
    if i < 1 then
      return true;   # finished with this iterator
    fi;
    stab!.pos[i] := stab!.pos[i]+1;
    stab!.point[i] := [];
    if stab!.pos[i] <= Length(stab!.info[i]) then
      return false;  # next element found
    fi;
    stab!.pos[i] := 1;
    i := i - 1;
  od;
  # this is never reached
end );


InstallGlobalFunction( OrbitsFromSeedsToOrbitList,
function( obsol, li, hashsize, grpsize )
  local o,orb,v;
  for v in li do
      orb := IsVectorInOrbitBySuborbitList(v,obsol);
      if orb = fail then
          o := OrbitBySuborbit(v,hashsize,grpsize,obsol.setup,50);
          if o <> "didnotfinish" then
              Add(obsol.obsos,o);
              Print("New suborbit:\n");
              ViewObj(o);
              Print("\nHave now ",Length(obsol.obsos),
                    " orbits with a total of ",
                    ORB_PrettyStringBigNumber(Sum(obsol.obsos,Size)),
                    " elements.\n");
          fi;
      else
          Info(InfoOrb,2,"Already know orbit ",orb);
      fi;
  od;
end );

InstallGlobalFunction( OrbitBySuborbit2,
function(setup,p,j,l,i,percentage)
  # Enumerates the orbit of p under the group U_j (with G=U_{k+1}) by
  # suborbits for the subgroup U_i described in "setup". 
  # "setup" is a setup object for the iterated quotient trick,
  #         effectively enabling us to do minimalization with a subgroup
  # "p" is a point
  # "l", "j" and "i" are integers with k+1 >= j >= l > i >= 1
  # "j" indicates in which representation we work,
  # "i" indicates how many helper subgroups we use
  # "l" indicates which group we enumerate
  # "percentage" is a number between 50 and 100 and gives a stopping criterium.
  #         We stop if percentage of the orbit is enumerated.
  #         Only over 50% we know that the stabilizer is correct!
  # Returns a suborbit database with additional field "words" which is
  # a list of words in gens which can be used to reach U-orbit in the G-orbit
  local assumestabcomplete,db,firstgen,fullstabsize,ii,lastgen,m,miniwords,
        mw,newperm,newword,o,oldtodo,pleaseexitnow,stab,stabg,stabgens,
        stabilizer,stabperms,sw,todo,v,words,x;

  Info(InfoOrb,2,"Entering OrbitBySuborbit2 j=",j," l=",l," i=",i);

  if not(j >= l and l > i and i >= 1) then
      Error("Need j >= l > i >= 1");
      return;
  fi;

  pleaseexitnow := false;  # set this to true in a break loop to
                           # let this function exit gracefully
  assumestabcomplete := false;  # set this to true in a break loop to
                                # let this function assume that the 
                                # stabilizer is complete

  # Setup some shortcuts:
  firstgen := Length(setup!.els[l-1])+1;
  lastgen := Length(setup!.els[l]);

  # A security check:
  if p <> setup!.op[j](p,setup!.els[j][1]^0) then
      Error("Warning: The identity does not preserve the starting point!\n",
            "Did you normalize your vector?");
  fi;

  # First we U_i-minimalize p:
  stab := rec();
  p := ORB_Minimalize(p,j,i,setup,stab,false);

  miniwords := [[]];  # here we collect U-minimalizing elements
  
  # Start a database with the first U-suborbit:
  db := SuborbitDatabase2(setup,j,l,i);
  StoreSuborbit(db,p,stab,1);

  stabgens := [];
  stabperms := [];
  stabilizer := Group(setup!.permgens[l][1]^0);
  if IsBound( setup!.stabchainrandom ) and setup!.stabchainrandom <> false then
      StabChain( stabilizer, rec( random := setup!.stabchainrandom ) );
  else
      StabChain(stabilizer);
  fi;
  fullstabsize := 1;
  
  words := [[]];
  todo := [[]];
  while true do

    ii := 1;
    while ii <= Length(todo) do
      if pleaseexitnow = true then 
          return ["didnotfinish",db,fullstabsize]; 
      fi;

      for m in [firstgen..lastgen] do
        x := setup!.op[j](p,setup!.els[j][m]);
        x := ORB_ApplyWord(x,todo[ii],setup!.els[j],
                           setup!.elsinv[j],setup!.op[j]);
        mw := [];
        x := ORB_Minimalize(x,j,i,setup,stab,mw);
        v := LookupSuborbit(x,db);
        if v = fail then   # a new suborbit
          Add(words,Concatenation([m],todo[ii]));
          Add(todo,Concatenation([m],todo[ii]));
          Add(miniwords,mw);
          StoreSuborbit(db,x,stab,fullstabsize);
          if 2 * TotalLength(db) * fullstabsize > setup!.size[l] and
             TotalLength(db) * fullstabsize * 100 >= 
                             setup!.size[l]*percentage then 
            Info(InfoOrb,2,"Leaving OrbitBySuborbit2");
            return Objectify( StdOrbitBySuborbitsType,
                       rec(db := db,
                       words := words,
                       stabsize := fullstabsize,
                       stab := stabilizer,
                       stabwords := stabgens,
                       groupsize := setup!.size[l],
                       orbitlength := setup!.size[l]/fullstabsize,
                       percentage := percentage,
                       seed := p ) );
          fi;
        else
          if assumestabcomplete = false and
             TotalLength(db) * fullstabsize * 2 <= setup!.size[l] then
            # otherwise we know that we will not find more stabilizing els.
            # we know now that v is an integer and that
            # p*setup!.els[m]*todo[ii]*U = p*words[v]*U
            # p*setup!.els[m]*todo[ii]*mw is our new vector
            # p*words[v]*miniwords[v] is our old vector
            # they differ by an element in Stab_U(...)
            stabg := List(stab.gens,
                          w->ORB_ApplyWord(setup!.els[j][1]^0,w,setup!.els[j],
                                           setup!.elsinv[j], OnRight ));
            o := Enumerate(Orb(stabg,x,setup!.op[j],
                   rec( hashlen := setup!.hashlen[j],
                        lookingfor := [Representatives(db)[v]],
                        schreier := true )));
            sw := TraceSchreierTreeForward(o,o!.found);
            sw := Concatenation( stab.gens{sw} );
            newword := Concatenation([m],todo[ii],mw,sw,
                            ORB_InvWord(miniwords[v]),ORB_InvWord(words[v]));
            Print("[\c");
            newperm := ORB_ApplyWord(setup!.permgens[l][1]^0,newword,
                            setup!.permgens[l],setup!.permgensinv[l],OnRight);
            if not(IsOne(newperm)) then
              Print(".\c");
              if not(newperm in stabilizer) then
                Print(".\c");
                Add(stabgens,newword);
                Add(stabperms,newperm);
                stabilizer := GroupWithGenerators(stabperms);
                Info(InfoOrb,1,"Calculating new estimate of the stabilizer...");
                if IsBound(setup!.stabchainrandom) and
                   setup!.stabchainrandom <> false then
                    StabChain(stabilizer, 
                              rec(random := setup!.stabchainrandom));
                else
                    StabChain(stabilizer);
                fi;
                fullstabsize := Size(stabilizer);
                Info(InfoOrb,1,"New stabilizer order: ",fullstabsize);
                if TotalLength(db) * fullstabsize * 100
                   >= setup!.size[l]*percentage then 
                  Info(InfoOrb,2,"Leaving OrbitBySuborbit2");
                  return Objectify( StdOrbitBySuborbitsType,
                         rec(db := db,
                             words := words,
                             stabsize := fullstabsize,
                             stab := stabilizer,
                             stabwords := stabgens,
                             groupsize := setup!.size[l],
                             orbitlength := setup!.size[l]/fullstabsize,
                             percentage := percentage,
                             seed := p) );
                fi;
              fi;
            fi;
            Print("]\c");
          fi;
        fi;
      od;   # for m in [firstgen..lastgen]
      ii := ii + 1;
    od;
  
    oldtodo := todo;
    todo := [];
    for ii in [1..Length(stabgens)] do
      Append(todo,List(oldtodo,w->Concatenation(stabgens[ii],w)));
    od;
    Info(InfoOrb,1,"Length of next todo: ",Length(todo));
  od;
  # this is never reached
end );


InstallGlobalFunction( ORB_ApplyUElement,
function(p,j,i,setup,stab,w)
  local ww;
  while i >= 1 do
    ww := ShallowCopy(setup!.trans[i][stab!.info[i][stab!.pos[i]]]);
    if IsList(w) then Append(w,ww); fi;
    p := ORB_ApplyWord(p,ww,setup!.els[j],setup!.elsinv[j],setup!.op[j]);
    i := i - 1;
  od;
  return p;
end );

[ zur Elbe Produktseite wechseln0.60Quellennavigators  Analyse erneut starten  ]