Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

share|improve this question
    
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... –  J. M. 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
show 2 more comments

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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