power set

[Martin Baker]

Is there any code in the FriCAS library to generate a power set from a set?
I could not find any so I wrote my own (see below). I probably need
custom code anyway to sort and filter the results.
My problem is that the only way I could work out how to do this is to
customise the list.spad code like this:
https://github.com/martinbaker/fricasAlgTop/blob/topology/list.spad#L295
Is there some way I can make a more standalone version of the following
code?
What I would like to do is replace 'S' with 'Type' but I don't think
that would work would it?

localPowerSets(j:List(S),filter:List(S)->Boolean): List(List S) ==
empty? j => list []
Sm := localPowerSets(rest j,filter)
Sn: List List S := []
for x in Sm repeat
if filter(x) then
Sn := cons(reverse cons(first j, x),Sn)
append(Sn, Sm)

gradeAndOrder(a:List S,b:List S) : Boolean ==
if #a < #b then return true
if #a > #b then return false
for ia in a for ib in b repeat
if S has OrderedSet then
if ia < ib then return true
if ia > ib then return false
false

powerSetFiltered(j:List(S),filter:List(S)->Boolean):List List S ==
map(reverse,sort(gradeAndOrder,localPowerSets(j,filter)))

powerSet(j:List(S)):List List S ==
powerSetFiltered(j,(x)+-> true)

[Prof. Dr. Johannes Grabmeier]

doesn't it suffice to construct all subsets from 0..n-1 for you?

(9) -> for k in 0..6 repeat for i in 0..binomial(6,k)-1 repeat print
subSet(6,k,i)
   []
   [0]
   [1]
   [2]
   [3]
   [4]
   [5]
   [1, 0]
   [2, 0]
   [2, 1]
   [3, 0]
   [3, 1]
   [3, 2]
   [4, 0]
   [4, 1]
   [4, 2]
   [4, 3]
   [5, 0]
   [5, 1]
   [5, 2]
   [5, 3]
   [5, 4]
   [2, 1, 0]
   [3, 1, 0]
   [3, 2, 0]
   [3, 2, 1]
   [4, 1, 0]
   [4, 2, 0]
   [4, 2, 1]
   [4, 3, 0]
   [4, 3, 1]
   [4, 3, 2]
   [5, 1, 0]
   [5, 2, 0]
   [5, 2, 1]
   [5, 3, 0]
   [5, 3, 1]
   [5, 3, 2]
   [5, 4, 0]
   [5, 4, 1]
   [5, 4, 2]
   [5, 4, 3]
   [3, 2, 1, 0]
   [4, 2, 1, 0]
   [4, 3, 1, 0]
   [4, 3, 2, 0]
   [4, 3, 2, 1]
   [5, 2, 1, 0]
   [5, 3, 1, 0]
   [5, 3, 2, 0]
   [5, 3, 2, 1]
   [5, 4, 1, 0]
   [5, 4, 2, 0]
   [5, 4, 2, 1]
   [5, 4, 3, 0]
   [5, 4, 3, 1]
   [5, 4, 3, 2]
   [4, 3, 2, 1, 0]
   [5, 3, 2, 1, 0]
   [5, 4, 2, 1, 0]
   [5, 4, 3, 1, 0]
   [5, 4, 3, 2, 0]
   [5, 4, 3, 2, 1]
   [5, 4, 3, 2, 1, 0]

Am 07.04.25 um 17:14 schrieb Martin Baker:

--
Mit freundlichen Grüßen

Johannes Grabmeier

Prof. Dr. Johannes Grabmeier,
Köckstraße 1, D-94469 Deggendorf
Tel. +49-(0)-991-2979584, Tel. +49-(0)-151-681-70756
Fax: +49-(0)-991-2979592

[Ralf Hemmecke]

Why would you make your code so complicated?

I would simply write:

T ==> Integer
pwrset(s: List T) : List List T ==
empty? s => [[]]
ps: List List T := pwrset rest s
t: T := first s
tps := [cons(t, p) for p in ps]
concat(ps, tps)

powerSet(l: List T): List List T == sort((x,y)+->#x<#y, pwrset sort l)

On 4/7/25 17:14, Martin Baker wrote:
>       localPowerSets(j:List(S),filter:List(S)->Boolean): List(List S) ==
>         empty? j => list []
>         Sm := localPowerSets(rest j,filter)
>         Sn: List List S := []
>         for x in Sm repeat
>           if filter(x) then
>             Sn := cons(reverse cons(first j, x),Sn)
>         append(Sn, Sm)

Why do you use "reverse" here?

Can you tell a reason for this filter function?

>       gradeAndOrder(a:List S,b:List S) : Boolean ==
>         if #a < #b then return true
>         if #a > #b then return false
>         for ia in a for ib in b repeat
>           if S has OrderedSet then
>             if ia < ib then return true
>             if ia > ib then return false
>         false
>
>       powerSetFiltered(j:List(S),filter:List(S)->Boolean):List List S ==
>         map(reverse,sort(gradeAndOrder,localPowerSets(j,filter)))

Again, why reverse?

>       powerSet(j:List(S)):List List S ==
>         powerSetFiltered(j,(x)+-> true)

If you want this "stand-alone" then you have to write a package with
parameter T around the above code.

Ralf

[Kurt Pagani]

There are some:

https://fricas.org/api/SetOfMIntegersInOneToN.html

https://fricas.org/api/GrayCode.html

mabye even more ...

But in principle you only have to produce the numbers 0..2^(N-1) in binary form and filter (index) your set by the 1's (present), 0 absent..

[Ralf Hemmecke]

> But in principle you only have to produce the numbers 0..2^(N-1) in binary
> form and filter (index) your set by the 1's (present), 0 absent..

In fact, if Martin needs to filter out some subsets, then filtering out
integers and only generating subsets for the integers that remain, might
even be faster.

groundset := [1,2,3,4]
subset(li, n) == [x for x in li for i in 0..#li-1 | bit?(n, i)]
sort((x,y)+->#x<#y or #x=#y and x<y,_
[subset(groundset, n) for n in 0..2^(#groundset)-1])

The question is whether sorting the subsets is needed.

Ralf

[Martin Baker]

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.

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).

So the sensible thing to do here is give up.
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.

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

[Kurt Pagani]

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>

[Martin Baker]

On 07/04/2025 22:34, Kurt Pagani wrote:
> 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).

I have done a quick search online and skimmed some of the papers. Since
no one has found a reason why this cannot work I will take some more
time and read them more carefully, the paper you mention above look
especially useful so thank you for that.

My initial thought (which I have not fully thought through) was to
handle finite, monster lattices in the same way that FriCAS already
handles finite monster groups.

So groups involve:
1) start with a set
2) define permutations on the set (generators)
3) compose generators to get all elements
4) represent as strong generators so that we can scale up.

So for finite lattices can we:
1) start with a set
2) define generators as maps which remove one element (instead of
permutations).
3) compose generators to get lattice (subset of power set)
4) Find a way to represent this more efficiently than sets of sets (is
there anything like stabilisers and orbits in this case).

I know that Birkhoff's representation theorem says that finite
distributive lattices can always be represented by sets of sets but I
guess there could be more efficient representations?

The papers about enumeration of finite topologies seem to use different
representations.
For example this one uses transitive digraphs:
https://dl.acm.org/doi/pdf/10.1145/363282.363311
and this one uses semi-tensor products of matrices:
https://www.mdpi.com/2227-7390/10/7/1143

Its very hard for me to judge which of these approaches would scale up
best on FriCAS but my intuition suggests that what works best for groups
might work best for lattices.

Martin