# Find all permutations with reversals / cyclic permutations removed

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!

-
DeleteDuplicates[ Permutations[Range[4]], #1 == InversePermutation[#2] &]? –  kguler Oct 11 '12 at 13:33
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. –  A friendly helper Oct 11 '12 at 13:47
@kguler: Apparently InversePermutation[] only works on Cycle[] objects... –  Guess who it is. Oct 11 '12 at 13:54
I see ... you meant reversion and right rotation - InversePermutation is quite unrelated. –  kguler Oct 11 '12 at 14:09
@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. –  kguler Oct 11 '12 at 14:21

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.

-