#20669: LatticePoset: add function to get all sublattices
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.3
Component: combinatorics | Resolution:
Keywords: latticeposet | Merged in:
Authors: Jori Mäntysalo | Reviewers: Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/all_sublattices | 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
Replying to [comment:5 tscrim]:
> Replying to [comment:4 jmantysalo]:
> > Replying to [comment:3 tscrim]:
> > > I think you should use a backtracking algorithm instead of a
recursion. It will be faster (and you don't have to constantly get things
like `self.cardinality()`), never run up against the Python maximum
recursion limit, and have better input (which `set()` and `0` should be
defaults anyways).
> >
> > Maximun recursion limit is 999 by default, and that is too small only
if we have a `ChainPoset(n)` with `n > 999`; recursion stack will have at
most as many steps as the lattice has elements. And it will have `2^999`
sublattices anyway, so this is not valid argument.
> People could want to do some partial tests on some really big example of
a lattice or wanted to run a month-long-type computation on a big lattice
(of which, there are a number of examples of finite exceptional cases that
I come across in my research where the easiest way to prove things can be
to do long computations).
Well, now it took only 20 seconds to make `ChainPoset(1000)`. So yes, it
is theoretically possible to run this kind of computations. But then,
recursion limit can be changed.
> > Of course I can change this to use backtracking, but... Then why not
move this to static sparce graphs class, if we really want as fast code as
possible?
>
> I have no inherent objects to this, but does the static sparse digraph
code have the capacity to do the meet and joins?
No, but that could be added. Or actually copied from current file. For
Frattini sublattices that would actually make sense.
---
Basic questions about all reviews: 1) Is Sage better with this or without?
2) If with, is there some ''easy'' steps to make it still better?
--
Ticket URL: <http://trac.sagemath.org/ticket/20669#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
