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$ 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$ Commented Oct 11, 2012 at 13:47
  • $\begingroup$ @kguler: Apparently InversePermutation[] only works on Cycle[] objects... $\endgroup$ Commented Oct 11, 2012 at 13:54
  • $\begingroup$ I see ... you meant reversion and right rotation - InversePermutation is quite unrelated. $\endgroup$ 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$ 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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.