# BruteForceSieve.txt
 # Version 1.2
 # Ken W. Smith
 # Begun in April 2006, 
 # Last modified May 14, 2006.
 #     To run this program, insert the following Read statement
 # Read("BruteForceSieve_DS.txt");

 Print("Reading file 'BruteForceSieve_DS.txt' \n");

 ############################################################
 # BruteForceSieve_DS( [v,cn], [v1,k,lambda], chain, threshold, printflag, WriteFile );
 ############################################################
 
  BruteForceSieve_DS := function( grouplist, parameterlist, chain, threshold, printflag, WriteFile )
  local v1, cn, v, k, lambda, multiplier, d1, d2, g, e, a, aa, ee, ns, chain_size, i, counter1, level, target, lift_counter, d_multiset, soln, s, partition, refinement, upbound, 
 CL, TL, PreSolution, PostSolution, FinalSolution, NSub, Starttime;
 
   v:= grouplist[1]; cn := grouplist[2];
   v1 := parameterlist[1]; k := parameterlist[2]; lambda := parameterlist[3];
   multiplier := v1/v;  # [v, cn] could be a homomorphic image of a group of order v1.
   g := SmallGroup( v, cn ); e := Elements( g );  
   a := AutomorphismGroup(g); aa := Action(a,e); ee:=Elements(aa);;
   CL := ConvolutionTable_f(g,e, x-> x^-1 );
   ns := NormalSubgroups(g);
   chain_size := Size(chain);
   # We create a list of Transversal lists, one for each subgroup in 'chain'  
   TL := ListWithIdenticalEntries( chain_size, [ ] );
   for i in [ 1.. chain_size ] do
     TL[i] :=  TransversalListSpecific( g, e, ns[chain[ i ]] );
   od; 

 ############################################################
 # Main loop
 ############################################################
 # Beginning at the top of the lattice of normal subgroups, 
 # we create all possible difference set images, working our
 # way down the chain.
 for level in [0 .. chain_size-2] do
   refinement := TL[ chain_size-level-1 ]; partition := TL[ chain_size-level ];
   upbound := Size( refinement[1] )*multiplier;

 if level =0 then PreSolution :=[ ListWithIdenticalEntries(k,1) ]; fi;
   target := ListWithIdenticalEntries( k-lambda, 1 );
   for i in [1..Size(refinement)] do 
     target := Concatenation( target,ListWithIdenticalEntries( upbound*lambda, i ) );
   od;
  # This list is based on indices.

    ############################################################
    # Print to file:
    Print("\nWorking on [", v, ", ", cn, "] at level ", level,
      " with PreSolution of size ", Size(PreSolution),"\n");
    Print("and target ", Collected(target),"\n");
    AppendTo(WriteFile,"\nWORKING ON LEVEL ", level,
      " with PreSolution of size ", Size(PreSolution),"\n", PreSolution,"\n");
    AppendTo(WriteFile,"and target ", Collected(target),"\n");
    ############################################################

  PostSolution := [ ];
  lift_counter:= 0; counter1 := Size(PreSolution);
  for d_multiset in PreSolution do
    Starttime := Runtime();
    ############################################################
    # For each prior solution 'd_multiset', we generate a list of
    # all solutions at the next level ('refinement') which contract
    # to the prior solution.  
    # Thus we create the full set of "lifts" of d_multiset.
    # Lift() takes a Cayley table CL acting on [1..v],
    # two partitions of [1..v], 'partition' and 'refinement'
    # the element 'd_multiset' of the group ring on the set 'partition',
    # written as a multiset,
    # the target element, 'target' of the group ring  on the set 'refinement'
    # and computes all solutions D in the refinement space
    # such that D*D = target where * is the operation of CL.
    # The last two numbers are 'threshold' and 'printflag'. 

    soln := Lift( CL, partition, refinement,  d_multiset, target, upbound, threshold, printflag );

    ############################################################
    lift_counter := lift_counter+1;
    ############################################################
    # Print to file:
    Print("[",v,",",cn,"]: ",lift_counter, " of ", counter1, ". Lift procedure took ", QuoInt( Runtime()-Starttime, 1000), " seconds.\n");
    Print("Returning ", Size(soln), " solutions.\n\n");
    AppendTo(WriteFile, lift_counter, " of ", counter1, ". Lift procedure took ", QuoInt( Runtime()-Starttime, 1000), " secs.\n");
    AppendTo(WriteFile, "   Returning ", Size(soln), " solutions.\n\n");
    ############################################################

    PostSolution := Union( PostSolution, soln );
  od;

    if level < chain_size-2 then

    ############################################################
    # Print to file:
    Print("Size of solution set (before reduction): ", Size(PostSolution),"\n"); 
    AppendTo(WriteFile, "Size of solution set (before reduction) at level ", level, " is ",Size(PostSolution),"\n");
    AppendTo(WriteFile, "Solution is \n", PostSolution,"\n");
    ############################################################
      
      # Here we reduce the number of solutions by using automorphisms of the group g
      # The group s is the subgroup of Aut(g) which stabilizes (as a set) the 
      # the normal subgroup which created the partition 'refinement'.
      NSub := refinement[1]; s := Stabilizer( aa, NSub, OnSets);

    ############################################################
    # Print to file:
    Print("Size of automorphism group is ", Size( s ),"\n"); 
    AppendTo(WriteFile, "Normal subgroup is ", refinement[1],"\n");
    AppendTo(WriteFile, "Automorphism group has size ", Size(s), "\n"); 
      PostSolution :=  Reduce( g, e, s, refinement, PostSolution );
    Print("There are ", Size(PostSolution), " reduced solutions. \n");
    AppendTo(WriteFile, "There are ", Size(PostSolution), " reduced solutions: \n", PostSolution,"\n");
    ############################################################

    if Size(PostSolution) = 0 then 
    ############################################################
    # Print to file:
      Print("NO SOLUTION at level ", level, " with normal subgroup ",chain[chain_size-level-1], " and quotient ", 
        IdGroup(g/ns[chain[chain_size-level-1]]),".\n");
      AppendTo(WriteFile, "******************\nNO SOLUTION at level ", level, " with normal subgroup ",
        chain[chain_size-level-1], " and quotient ", 
        IdGroup(g/ns[chain[chain_size-level-1]]),".\n");
    ############################################################
    fi;

    else   # We are at the bottom of the lattice and are looking at difference sets
           # Here s is equal to aa and we are checking for equivalence.
    ############################################################
    # Print to file:
    Print("Size of solution set (before reduction): ", Size(PostSolution),"\n"); 
    Print("Automorphism group has size ", Size( a ), "\n"); 
    AppendTo(WriteFile, "Size of solution set (before reduction):",Size(PostSolution),"\n");
    AppendTo(WriteFile, "Solution is \n", PostSolution,"\n");
    AppendTo(WriteFile, "Automorphism group has size ", Size( a ), "\n"); 
    ############################################################

      FinalSolution := [ ];
      if multiplier > 1 then 
        FinalSolution :=  Reduce( g, e, s, refinement, PostSolution );
      else;
        for d1 in PostSolution do 
          d2 := MaxValueOnSets( g, e, aa, d1 ); 
          Add( FinalSolution, d2 );
        od;
      fi;
      PostSolution:=Set( FinalSolution );
    fi;
   PreSolution := ShallowCopy( PostSolution );
   od; # End of main loop
   return PostSolution;
 end;