2
$\begingroup$

Is there a good algorithm for generating all and only the unique permutations of a finite set respecting some kind of symmetry? For example, in Klondike solitaire, the two black suits are interchangeable, the two red suits are interchangeable, and the black suits are interchangeable with the red suits. This results in 4 symmetries, but from a unique game perspective we only need to generate one representative. Ideally this generator would be countable (identify how many permutations there are), and skippable (go to the Nth permutation without generating intermediary permutations)?

$\endgroup$
  • $\begingroup$ Can you formalize what you mean by "some kind of symmetry"? $\endgroup$ – Yuval Filmus Jan 17 '17 at 8:12
  • $\begingroup$ Is that not the same as all suits are interchangeable? $\endgroup$ – paparazzo Jan 17 '17 at 10:16
  • $\begingroup$ @YuvalFilmus: To formalize 'some kind of symmetry' I mean that we can transpose some subset of elements with another subset of elements of equal size and get a result that we can afford to ignore. For example, imagine in the space of permutations of { 1, 2, 3, 4 }, we might for some reason view the odd numbers as interchangeable with the even numbers one greater than themselves, but only if they are fully swapped, so e.g. we could think of { 1, 2, 3, 4 } ~ { 2, 1, 4, 3}, $\endgroup$ – amashi Jan 17 '17 at 22:43
  • $\begingroup$ @Paparazzi: it is not the same as all suits are interchangeable, which would allow e.g. {Clubs -> Hearts, Spades->Spades, Hearts->Diamonds, Diamonds->Clubs}, which would be a different game. However, I'm looking for a technique that would allow me to encode that condition as well. $\endgroup$ – amashi Jan 17 '17 at 22:52
  • $\begingroup$ Just because I don't understand does not mean it is wrong. Cheers $\endgroup$ – paparazzo Jan 18 '17 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.