On Monday, 7 April 2025 at 20:09:40 UTC+2 Martin Baker wrote:
Thank you for all your replies, I will have experiment with the
different options you have given but I think all 3 of you are pointing
me in the direction of working in (non-negative?) integers and then
using them to index back into the original set at the end.
I would never have thought of looking for the subSet function in
SymmetricGroupCombinatoricFunctions for instance.
I think it would be helpful to other users if one of the algorithms
suggested could be wrapped in a function called powerSet and put in the
set domain.
Would this really be worthwile? Maybe for tiny sets ... however, actually
it's almost a one-liner when performance isn't important, e.g.
powerSet(s) ==
empty? s => [s]
concat(p:=powerSet(rest s),[cons(first s,x) for x in p])
(3) -> #powerSet expand(1..22)
(3) 4194304
Type:
PositiveInteger
(4) -> powerSet [A,B,C,D]
Compiling function powerSet with type List(OrderedVariableList([A,B,
C,D])) -> List(List(OrderedVariableList([A,B,C,D])))
(24)
[[], [D], [C], [C, D], [B], [B, D], [B, C], [B, C, D], [A], [A, D], [A,
C],
[A, C, D], [A, B], [A, B, D], [A, B, C], [A, B, C, D]]
Type:
List(List(OrderedVariableList([A,B,C,D])))
(5) ->
But it will run quickly out of time and space ;-) Displaying 2^22=4194304
subsets might already be a challenge, so I think it's more harm- than
useful.
Maybe you'll find a good and safe algorithm. Rosetta is inspiring
https://rosettacode.org/wiki/Power_set (the Common-Lisp ones are really
elegant :).
On 07/04/2025 17:56, 'Ralf Hemmecke' via FriCAS - computer algebra
system wrote:
> The question is whether sorting the subsets is needed.
I think it would be helpful for human readability if the results are
graded by set length and are in a consistent order.
In most cases I can think of filtering would not be required, for
instance, generating a discrete topology.
However there is one, completely mad, case that I would like to try even
though I know its probably doomed.
When I was trying to get an intuitive intuition for topologies on a
finite set I thought it would help if I could write a function that
listed out all the topologies on a set, of a given length, and see how
they relate to each other.
When I looked this up on wikipedia I found that the number of topologies
is massive, even on a small set:
https://en.wikipedia.org/wiki/Finite_topological_space#Number_of_topologies_on_a_finite_set
Also finding an efficient algorithm to do this is an unsolved problem (I
thought there were no unsolved problems in point-set topology).
I assume you have read
https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements
There are many unsolved problems, e.g.
https://staff.fnwi.uva.nl/j.vanmill/papers/papers1990/opit.pdf (digital).
So the sensible thing to do here is give up.
Not necessarily. From a computational point of view there is certainly a
lack of a concise package that covers the essentials, like
https://www.math.uchicago.edu/~may/MISC/FiniteSpaces.pdf (you surely know
it).
However even if no one has found an efficient algorithm there is still
the inefficient bruit-force algorithm. That is to take every possible
combination (a power set of a power set !) and then filter the result to
pick only those that are valid topologies. I would also like to filter
the results to give only topologies that are T0 and to not add
topologies if there is already one isomorphic to it (another very
difficult problem) this would reduce the size of the list a lot.
Because the lists are so massive I think the results need to be filtered
as the list is being generated. Not construct a really big list and then
filter it.
Yet, you'll need a lot of RAM ... even modest lists may exhaust the heap,
unless you use smart algorithms รค la Gray code for instance.
(7) -> #powerSet expand(1..30)
Heap exhausted during garbage collection: 0 bytes available, 16 requested.
Greetings from ldb>
I realise this could only work for very small sets (3 or 4) but, for
some reason, it seems like something I could learn from even though its
mad.
Martin
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/7348b61b-e701-4e8f-9a5e-958fabb0c309n%40googlegroups.com.
