Edit detail for #296 PERMGRP should compute cycle indicator polynomial revision 1 of 1

changed:
-
It would be nice if 'PERMGRP' could generate the cycle indicator polynomial for a given permutation group.

Furthermore, it should be able to list all the elements of a given permutation group as a stream.

Finally, it should be able to reduce the set of given generators to a minimal set.

For the first two items I have a brute force solution, there might be better ones, of course. I guess that all of this will be merged into the combinat package. Here is the code, for those who want to play with it::

  -- generate all permutations given the generators
  
  -- multiply each of the elements in result by each of the generators
  listaux(gens: List PERM INT, result: List PERM INT): List PERM INT ==
    removeDuplicates(append(result, reduce(append, [[p*q for q in result] for p in gens])))
  
  list(gens: List PERM INT): List PERM INT ==
    result := [1$PERM INT]
    lold := 0
    lnew := 1
    while lnew > lold repeat
      result := listaux(gens, result)
      lold := lnew
      lnew := #(result)$List PERM INT
  
    result
  
  -- collect cyclePartitions into the cycle indicator polynomial
  
  cyclePoly(lp: List Partition, vars: List POLY INT): POLY INT ==
    n := #vars
    p := lp.1
    c := 1
    result := 0
    for q in rest lp repeat
      if q = p then 
        c := c+1
      else 
        fix := n-reduce(+, p::List INT, 0)
        result := result + c * reduce((a,b) +-> a*b, _
                                      [vars.i for i in p::List INT],  _
                                      (vars.1)**fix)
        p := q
        c := 1
  
    fix := n-reduce(+, p::List INT)
    result := result + c * reduce((a,b) +-> a*b, _
                                  [vars.i for i in p::List INT], _
                                  (vars.1)**fix)

Martin

  -- generate all permutations given the generators

  -- multiply each of the elements in result by each of the generators
  listaux(gens: List PERM INT, result: List PERM INT): List PERM INT ==
    removeDuplicates(append(result, reduce(append, [[p*q for q in result] for p in gens])))

  list(gens: List PERM INT): List PERM INT ==
    result := [1$PERM INT]
    lold := 0
    lnew := 1
    while lnew > lold repeat
      result := listaux(gens, result)
      lold := lnew
      lnew := #(result)$List PERM INT

    result

  -- collect cyclePartitions into the cycle indicator polynomial

  cyclePoly(lp: List Partition, vars: List POLY INT): POLY INT ==
    n := #vars
    p := lp.1
    c := 1
    result := 0
    for q in rest lp repeat
      if q = p then 
        c := c+1
      else 
        fix := n-reduce(+, p::List INT, 0)
        result := result + c * reduce((a,b) +-> a*b, _
                                      [vars.i for i in p::List INT],  _
                                      (vars.1)**fix)
        p := q
        c := 1

    fix := n-reduce(+, p::List INT)
    result := result + c * reduce((a,b) +-> a*b, _
                                  [vars.i for i in p::List INT], _
                                  (vars.1)**fix)