finite-axiom-of-choice.gap

# リストlistの置換permによる像を求める
ImageUnderPermutation := function(list, perm)
    return List(list, x -> x^perm);
end;

# 置換群groupのある元によってlistが動くならtrueを返す
VarianceUnderSomePerm := function (group, list)
    local perm;
    for perm in Elements(group) do
        if Set(ImageUnderPermutation(list, perm)) <> Set(list) then
            return true;
        fi;
    od;
    return false;
end;

# [1..n]の任意のm元部分集合について、それが置換群groupのある元によって動くならtrueを返す
VarianceUnderSomePermForallComb := function (group, n, m)
    local x;
    for x in Combinations([1..n], m) do
        if not VarianceUnderSomePerm(group, x) then
            return false;
        fi;
    od;
    return true;
end;

n := 5;
m := 2;
Print("n="); Print(n); Print(", m="); Print(m); Print("\n");
G := SymmetricGroup(n);
for H in List(ConjugacyClassesSubgroups(G), Representative) do
    Print(H);
    Print(": ");
    Print(VarianceUnderSomePermForallComb(H, n, m));
    Print("\n");
od;

~result.txt

n=5, m=2
Group( () ): false
Group( [ (4,5) ] ): false
Group( [ (1,4)(2,3) ] ): false
Group( [ (2,5,4) ] ): false
Group( [ (1,3)(2,4), (1,4)(2,3) ] ): true
Group( [ (1,2,4,3) ] ): true
Group( [ (1,2), (3,4) ] ): false
Group( [ (1,2,4,5,3) ] ): true
Group( [ (1,2), (1,2,3) ] ): false
Group( [ (1,3)(4,5), (1,2,3) ] ): false
Group( [ (1,4)(2,5,3) ] ): false
Group( [ (3,4), (1,4)(2,3) ] ): true
Group( [ (1,3)(2,4), (1,2,5,4,3) ] ): true
Group( [ (1,2,3), (1,4)(2,3) ] ): true
Group( [ (1,2), (3,5,4), (4,5) ] ): false
Group( [ (1,3)(4,5), (1,2,4,3) ] ): true
Group( [ (1,3,2), (1,2,4,3) ] ): true
Group( [ (1,4)(2,3), (2,5,4) ] ): true
Group( [ (4,5), (1,2,4,3) ] ): true