R: list all directionless circular permutations/arrangements (i.e. where clockwise/anti-clockwise are the same)

Question

How do I list all the circular permutations in R where direction does not matter? I have a vector 1:4 for illustration (however, I would like a general solution). I use

gtools::permutations(n = 4, r = 4)

which gives me a listing of all possible permutations as follows:

     [,1] [,2] [,3] [,4]
 [1,]    1    2    3    4
 [2,]    1    2    4    3
 [3,]    1    3    2    4
 [4,]    1    3    4    2
 [5,]    1    4    2    3
 [6,]    1    4    3    2
 [7,]    2    1    3    4
 [8,]    2    1    4    3
 [9,]    2    3    1    4
[10,]    2    3    4    1
[11,]    2    4    1    3
[12,]    2    4    3    1
[13,]    3    1    2    4
[14,]    3    1    4    2
[15,]    3    2    1    4
[16,]    3    2    4    1
[17,]    3    4    1    2
[18,]    3    4    2    1
[19,]    4    1    2    3
[20,]    4    1    3    2
[21,]    4    2    1    3
[22,]    4    2    3    1
[23,]    4    3    1    2
[24,]    4    3    2    1

However, what I would like is the listing of the six circular permutations. So, I think that this is:

cbind(gtools::permutations(n = 3, r = 3),4)

that gives me:

    [,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    3    2    4
[3,]    2    1    3    4
[4,]    2    3    1    4
[5,]    3    1    2    4
[6,]    3    2    1    4

However, I would like to also ignore the listings which are the same but for order. Example: I do not want to distinguish c(1,2,3,4) from c(4,3,2,1) (i.e. the 1st and the 6th entry), or c(1, 3, 2, 4) and c(2, 1, 3, 4) (i.e. the 2nd and the 4th entry) and c(2, 1, 3, 4) from c(3, 1, 2, 4) (i.e. the 3rd and the 5th entry in the output)? Is it simply a case of taking the first half of the results?

Is there a surer way of doing this? Many thanks for answering my question or providing suggestions.

Iaroslav Domin · Accepted Answer · 2021-08-28T18:09:47.123

We can't simply take the first half of results of permutations(n-1, n-1) and append n. This is easy to see for n = 5.

I suggest to use the following approach:

We set the first element to always be 1. This way we make sure that we take only 1 permutation for each set of equivalent permutations. That's basically the same as you did making 4 the always be the last element in your example.
Consider only such permutations for which element #2 is less than element #n. For each permutation in the set described by the first rule there will be one and only one permutation which is reverse to it. This way we make sure to only take one permutation for each such pair.

And this is the algorithm we are going to use to construct such set of permutations:

Find all pairs of elements #2 and #n, where #2 is less then #n. This is combinations(n-1, 2, v = 2:n).
For each such combination find all permutations of all the rest n-3 elements. This is permutations(n - 3, n - 3, v = rest_elements) where rest_elements is a vector listing all n-3 elements that are left when we remove 1, #2 and #n.

library(gtools)
get_perms <- function(n) {
  # 1 is always first, #2 and #n have to be such that #2 < #n
  # all combinations of elements #2 and #n:
  combs_2n <- combinations(n-1, 2, v = 2:n)
  # for each such combination we have n-3 elements left to place
  # it's (n-3)! variants
  n_perms_rest <- factorial(n - 3)
  # resulting matrix with placeholders for these element combinations
  res <- 
    cbind(
      1, # element 1
      rep(combs_2n[,1], each = n_perms_rest), #element 2
      matrix(nrow = n_perms_rest*nrow(combs_2n), ncol = n-3), # elements 2-(n-1)
      rep(combs_2n[,2], each = n_perms_rest)
    )
  # fill placeholders
  for (i in 1:nrow(combs_2n)) {
    rest_elements <- setdiff(2:n, combs_2n[i,])
    rest_perms <- permutations(n - 3, n - 3, v = rest_elements)
    res[1:n_perms_rest + (i-1)*n_perms_rest, 3:(n - 1)] <- rest_perms
  }
  res
}

get_perms(5)
#>       [,1] [,2] [,3] [,4] [,5]
#>  [1,]    1    2    4    5    3
#>  [2,]    1    2    5    4    3
#>  [3,]    1    2    3    5    4
#>  [4,]    1    2    5    3    4
#>  [5,]    1    2    3    4    5
#>  [6,]    1    2    4    3    5
#>  [7,]    1    3    2    5    4
#>  [8,]    1    3    5    2    4
#>  [9,]    1    3    2    4    5
#> [10,]    1    3    4    2    5
#> [11,]    1    4    2    3    5
#> [12,]    1    4    3    2    5

^{Created on 2021-08-28 by the reprex package (v2.0.1)}

@user3236841 i updated my anwer, taking half of results of `permutations` won't work for n >= 5 — Iaroslav Domin, Aug 28 '21 at 18:12
Wow! Thanks! What about the general case when we take r out n in our circular arrangement? — user3236841, Aug 28 '21 at 18:26
This essentially boils down to finding all such permutations for r out of r and then relabelling them for all combinations of r elements of n. — Iaroslav Domin, Aug 28 '21 at 20:39
So there would be choose(n, r) x (r-1)!/2 many of these? I think that the code may still be interesting! — user3236841, Aug 29 '21 at 00:01

R: list all directionless circular permutations/arrangements (i.e. where clockwise/anti-clockwise are the same)

1 Answers1