How is GAP generating all subgroups?
GAP stores precomputed lists of subgroups of (automorphism groups) of a number of simple subgroups, the rest is computed on the fly. However it uses far more group theory than only considering subsets. (For reasons of memory use, GAP will calculate subgroup only up to conjugacy by default.)
The methods use (very roughly) follow the following strategy:
If $G$ has an elementary abelian normal subgroup $N\lhd G$, every subgroup $U$ as an image $A=UN/N$ in $G/N$ and an intersection $B=U\cap N$. Recursively calculate subgroups of $G/N$, as well as of $N$ (this is a vector space) and for every pair $(A,B)$ with $A/N\le G/N$ and $B\le N$ such that $B\lhd A$ calculate complements to $N/B$ in $A/B$ using cohomology.
If $G$ has no solvable normal subgroup, then the socle $S=Soc(G)$ is a direct product of simple groups. Calculate subgroups of $S$ as subdirect products of subgroups of the simple factors, and then for each subgroup consider subgroups of $N_G(S)/N$.
The subgroups of the simple factors are stored.
Two articles describing the process (Caveat: author bias) are:
MR1806212 Cannon, John J.; Cox, Bruce C.; Holt, Derek F. Computing the subgroups of a permutation group. J. Symbolic Comput. 31 (2001), no. 1-2, 149–161.
MR3206359 Hulpke, Alexander Calculation of the subgroups of a trivial-fitting group. ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, 205–210, ACM, New York, 2013.
A couple things:
I highly doubt they precompute S4. You're right the naive approach is bad, and they likely don't use that either. I won't try to develop a better algorithm here, but it seems like there might be a slightly less naive way to find all of the distinct generating sets via dynamic programming, which I'd imagine would be reasonably efficient in comparison.
GAP is open source (hosted on Github here), so it's actually not that difficult to look into how the literal computations themselves work. The "AllSubgroups" command is defined in this file. It appears to rely on in a key way the
ConjugacyClassesSubgroupsmethod from this file. That being said, I don't know the syntax of GAP, so someone else would have to analyze those particular files better.Looking through the code, I saw a reference to a paper on better methods for computing normal subgroups, which is here. I think I saw a reference to them using the underlying method here, but this may no longer be the state of the art. Still, for the theoretical side of (part) of what GAP does, this is probably the best bet.