11
$\begingroup$

I have a list of all non-cyclic permutations of n labels. How can I get rid of all elements which are redundant in the sense that they are the inverse of another one. For instance if n=4, the elements {1,2,3,4} and {1,4,3,2} are related by reversal and right rotation by one element. So I want to discard the latter.

Cheers!

Improve this question
$\endgroup$
7
  • $\begingroup$ DeleteDuplicates[ Permutations[Range[4]], #1 == InversePermutation[#2] &]? $\endgroup$
    – kglr
    Commented Oct 11, 2012 at 13:33
  • $\begingroup$ If I use DeleteDuplicates[ Permutations[Range[4]], #1 == RotateRight[Reverse[#2]] &] it works, i.e. it kills all the entries which are the same under inversion :) For some reason InversePermutation does not do the trick. $\endgroup$
    – A friendly helper
    Commented Oct 11, 2012 at 13:47
  • $\begingroup$ @kguler: Apparently InversePermutation[] only works on Cycle[] objects... $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Oct 11, 2012 at 13:54
  • $\begingroup$ I see ... you meant reversion and right rotation - InversePermutation is quite unrelated. $\endgroup$
    – kglr
    Commented Oct 11, 2012 at 14:09
  • 1
    $\begingroup$ @J.M. that's the impression one gets from the docs; but it works with permutation lists too. You can see this by replacing the Cycle[] objects with the associated permutation lists in all the examples in docs, or checking PermutationProduct[#, InversePermutation[#]]& with cycles and/or lists as input. $\endgroup$
    – kglr
    Commented Oct 11, 2012 at 14:21

1 Answer 1

Reset to default
5
$\begingroup$

I believe what you want can be done by placing the permutations into a canonical form before running DeleteDuplicates, as I explained in How to represent a list as a cycle.

Here with the addition of Reverse:

primaryPermutations[a_List] :=
  Module[{f1, f2},
    f1 = RotateLeft[#, Ordering[#, 1] - 1] &;
    f2 = # ~Extract~ Ordering[#, 1] &[f1 /@ {#, Reverse@#}] &;
    DeleteDuplicates[f2 /@ a]
  ]

Use:

Permutations @ Range @ 4 // primaryPermutations

{{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}}

A faster approach may be to generate these "primary" permutations directly, then extract those that are present in your list using Intersection.

Improve this answer
$\endgroup$

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.