6
$\begingroup$

I have a permutation group, e.g.

g = PermutationGroup[{Cycles[{{1, 2}}]}]

but not necessarily limited to a single generating cycle.

What I want is to create a list of subsets of some integers, for instance {1,2,3}, modulo this group g. I know I can create all subsets of this list of, say, length 2, via

Subsets[{1,2,3},{2}] (*  == {{1, 2}, {1, 3}, {2, 3}}  *)

Under the action of g, the last two items are considered equivalent, as one can map 1<->2.

How do I do this, ideally without filtering a list of all possible subsets (as those blow up exponentially when the list of integers becomes longer)?

Thanks a lot!

/J

Edit: I found a paper that yields an algorithm, if anyone has an idea on how to implement this efficiently in a Mathematica way?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I'm afraid this solution is precisely the "filtering all possible subsets" you mentioned...

Given an arbitrary group g and a list s of seeds, I think you need

First /@ GroupOrbits[g, s]

As you say, the worst case is when the list s is the list of all possibilities, in your case

s = Subsets[{1, 2, 3}, {2}]

I'm assuming that you don't want tuples with repeated elements, like {1, 1}, say.

Depending on the group you have, perhaps you can start with a simpler list s.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the input! I'm not sure I follow the first proposal, though: It would just give me one coset, no? $\endgroup$
    – J Bausch
    Commented Dec 8, 2018 at 0:16
  • $\begingroup$ No. GroupOrbits is partitioning the set of all subsets into orbits of equivalent subsets. And then we are mapping First to select the first element of each orbit, hence ignoring all other equivalent subsets, which is what you wanted (I think). You can partition a group into cosets, but the operation of partitioning a list of any type of elements into orbits under an action of a group is a more general operation, and this is what is being done here. In this case we are partitioning the list of all 2-subsets of {1, 2, 3}. $\endgroup$
    – jose
    Commented Dec 8, 2018 at 17:01
  • $\begingroup$ You're right, of course. I don't want the group orbits on elements, but on permutations; so I'd have to take First/@GroupOrbits[g, s, Permute]. But the problem remains, I don't want to filter, but generate. I found a paper which, I believe, explains this: arxiv.org/abs/1211.6261 $\endgroup$
    – J Bausch
    Commented Dec 9, 2018 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.