denisrosset / alasc Goto Github PK

View Code? Open in Web Editor NEW

21.0 21.0 3.0 1.75 MB

Computational Group Theory in Scala. It's Scala permuted!

Scala 100.00%

combinatorics group-theory group-theory-algorithms permutation-algorithms permutation-groups permutations scala

alasc's People

Contributors

Stargazers

Watchers

Forkers

gitter-badger mcanlas sashakolpakov

alasc's Issues

Add hashCode to Domain#Partition, PartitionMap

Add missing hashCode to those, and maybe other classes in Alasc

Bugs in RepresentativesSeq with large jumps in the BSGS chain

Observed in Faacets using the Chen2008 inequality for 5 outputs.

Reduce allocations when traversing the chain ownGenerators / strongGeneratingSet.

This method dominates in the number of allocations, allocating SeqViewLike and friends.

Idea: implement everything as Iterables at the top level, using iterators on the nodes.

Grp.contains is not safe when using different actions

It's not a given that the action used to represent the group can represent the provided element as well.

Revise API of Grp.findSameAction

Move implicit PermutationAction[Q] to explicit parameter.

Allow computation of centralizers, conjugates... when the provided element(s) are not part of the group

Right now, areConjugate, findConjugation, centralizer assume that g (or g1, g2) are elements of grp.

This can be relaxed by

Checking whether the provided elements are contained in the group. If so, proceed as now.
If not, recompute a faithful action for the group that is compatible with the provided elements, and proceed to the computation.

Add suggestion of representation for GrpLazy, e.g. when calling Grp.fromGenerators.

This is to avoid recomputation of representations from generators in code where the representation is fixed.

All uses of Grp.fromChain should provide the representation

Verify that this is the case everywhere.

Are all objects safe to serialize ?

Probably not, some can keep closures (ex: LazyGroup with random element function). Before using serialization, an audit should be performed.

Allow arbitrary bases in Group and BSGS.

Perm.fromImages should have a similar signature to the tabulate method.

All uses of Grp.fromChain should provide the original (better looking?) generators

Remove need for ClassTag by boxing everything in group construction

Replace `BigInt` by `SafeLong`

There is no reason to prefer BigInt, as SafeLong is faster.

Implement default method to find a moved point in PermutationAction.

Master branch difficult to bootstrap

Hi, not sure if I'm doing something wrong but I don't think the dependencies (I think qalg and/or metal) are not published anywhere, and themselves are not stable/building. What can be done to have a stable base core? Are we waiting for something upstream (Cats)?

Duplicates in constructor result in an infinite loop

Perm(3,4,5,3)

result in an infinite loop that eventually consumes all memory.

We should probably filter duplicates or throw an IllegalArgumentException.

Stack trace for the above:

java.lang.OutOfMemoryError: GC overhead limit exceeded
  at scala.collection.immutable.List.$colon$colon(List.scala:112)
  at net.alasc.perms.Cycle$.rec$1(Cycle.scala:96)
  at net.alasc.perms.Cycle$.orbit(Cycle.scala:98)
  at net.alasc.perms.Cycles$.rec$1(Cycles.scala:103)
  at net.alasc.perms.Cycles$.fromSupportAndImageFun(Cycles.scala:108)
  at net.alasc.perms.internal.GenPrmOps$.toCycles$extension(GenPrmOps.scala:52)
  at net.alasc.perms.Perm.toString(Perm.scala:17)
  at scala.runtime.ScalaRunTime$.inner$1(ScalaRunTime.scala:250)
  at scala.runtime.ScalaRunTime$.stringOf(ScalaRunTime.scala:255)
  at scala.runtime.ScalaRunTime$.replStringOf(ScalaRunTime.scala:263)
  at .$print$lzycompute(<console>:10)
  at .$print(<console>:6)
  at $print(<console>)
  at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
  at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
  at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
  at java.lang.reflect.Method.invoke(Method.java:498)
  at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:735)
  at scala.tools.nsc.interpreter.IMain$Request.loadAndRun(IMain.scala:999)
  at scala.tools.nsc.interpreter.IMain.$anonfun$interpret$1(IMain.scala:567)
  at scala.tools.nsc.interpreter.IMain$$Lambda$4658/2087216452.apply(Unknown Source)
  at scala.reflect.internal.util.ScalaClassLoader.asContext(ScalaClassLoader.scala:34)
  at scala.reflect.internal.util.ScalaClassLoader.asContext$(ScalaClassLoader.scala:30)
  at scala.reflect.internal.util.AbstractFileClassLoader.asContext(AbstractFileClassLoader.scala:33)
  at scala.tools.nsc.interpreter.IMain.loadAndRunReq$1(IMain.scala:566)
  at scala.tools.nsc.interpreter.IMain.interpret(IMain.scala:593)
  at scala.tools.nsc.interpreter.IMain.interpret(IMain.scala:563)
  at scala.tools.nsc.interpreter.ILoop.interpretStartingWith(ILoop.scala:886)
  at scala.tools.nsc.interpreter.ILoop.command(ILoop.scala:754)
  at scala.tools.nsc.interpreter.ILoop.processLine(ILoop.scala:456)
  at scala.tools.nsc.interpreter.ILoop.loop(ILoop.scala:477)
  at scala.tools.nsc.interpreter.ILoop.process(ILoop.scala:1069)