3

How do I find all the permutations of a list excluding cyclic permutations?

This problem has arisen due to a coding project I'm working on. I'm currently unsure if this was more appropriate for the math stack exchange or the coding one however the answer I'm looking for is (hopefully) very maths based which is why I'm here, though do let me know if it would sit better in stack overflow. I have done my research but most of the things that I've looked at are either beyond my understanding of code and/or math so a simple logical solution would help a lot!

So far, I've realized that to find the permutations excluding cyclic ones can be found by removing the first element (say $[1,2,3,4] \to [2,3,4]$), and permuting the remaining subset, appending the removed element to the beginning of each permutation ($[1,2,3,4], [1,2,4,3], [1,3,2,4], [1,3,4,2]$ etc...). This method, however breaks down when duplicate numbers appear: $[1,1,2,3]$, with this method becomes: $[1,1,2,3], [1,1,3,2], [1,2,3,1], [1,2,1,3], [1,3,1,2], [1,3,2,1]$; and we can see that $[1,1,2,3]$ is cyclic to $[1,2,3,1]$. This list should be $[1,1,2,3], [1,1,3,2], [1,2,1,3]$.

I'm looking for a method that can do this (without duplicates if possible) and an equation to find the number of non-cyclic permutations given a list without actually finding them.

Apologies if my mathematical language is incorrect, feel free to correct me!

Arctic Char
  • 16,007
Mixnik
  • 75
  • Specifically you're looking to remove cycles of length $n$ from the set of $n$ permutations? – CyclotomicField Nov 25 '21 at 20:37
  • This method misses a lot of permutations. For instance 1234 -> 2134 is not represented by this algorithm. In any case, just to clarify: do you want to exclude permutations such as 12345 -> 34512 as well? But not excluding, presumably, permutations such as 12345 -> 24135 (which would be excluded under CyclotomicField's suggestion) – Eric Nathan Stucky Nov 26 '21 at 03:12
  • @mixtli Can you confirm whether mine or Eric Nathan Stucky’s interpretation is the correct one? – Milten Nov 27 '21 at 11:32
  • There seems to a bit of confusion here. As I understand it, we want all permutations, but without duplicates up to cyclic shifting. In other words, we want all ways to lay a round dinner table with the numbers, so to speak. Mixtli, is this right? – Milten Nov 27 '21 at 11:37
  • 1
    https://stackoverflow.com/q/3467914 Like this? – Milten Nov 27 '21 at 11:42
  • 2
    Eric Nathan Stucky I see the confusion, What I'm looking for is an algorithm of sorts that in essence would generate all the permutations and then cancel out the ones that are the same as others if cycled any number of times (e.g 1234, 2341, 3412, 4123 are all cycles of each other so only 1234 should appear in my final list as all these cyclic permutations are represented by 1234), so your example of 1234 -> 2134 would be represented by the algorithm because 2134 is a cyclic permutation of 1342 which would appear in the algorithm – Mixnik Nov 27 '21 at 11:56
  • Understood, thanks! – Eric Nathan Stucky Nov 27 '21 at 11:58
  • @Milten, Yes that stack overflow question seems to be what I'm looking for! Though an initial look through the solution's paper (http://www.cis.uoguelph.ca/~sawada/papers/alph.pdf) makes it seem quite complex? – Mixnik Nov 27 '21 at 12:14
  • @Mixtli I think the fact is just that this is not a very simple question. But notice that the paper has an explicit formula for the number (i.e. $N()$), and also the simplified but slower algorithm SimpleFixedContent. Why don’t you take a closer look at those and then give questions as needed? There is a chance something simpler might be possible, since the algorithms in the paper return specifically the lexicographically smallest representatives - but I wouldn’t really count on it personally. – Milten Nov 27 '21 at 12:28

0 Answers0