Блог

Как мне перечислить все круговые перестановки в R, где направление не имеет значения? У меня есть вектор 1:4 для иллюстрации (однако я хотел бы получить общее решение). Я использую

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

что дает мне список всех возможных перестановок следующим образом:

      [,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
 

Однако то, что я хотел бы, — это список из шести круговых перестановок. Итак, я думаю, что это:

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

это дает мне:

     [,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
 

Тем не менее, я хотел бы также игнорировать списки, которые являются одинаковыми, но для порядка. Пример: я не хочу отличать c(1,2,3,4) от c(4,3,2,1) (т. е. 1-я и 6-я записи) или c(1, 3, 2, 4) и c(2, 1, 3, 4) (т. е. 2-я и 4-я записи) и c(2, 1, 3, 4) от c(3, 1, 2, 4) (т. е. 3-я и 5-я записи в выводе)? Является ли это просто случаем получения первой половины результатов?

Есть ли более надежный способ сделать это? Большое спасибо за ответ на мой вопрос или предложения.

Мы не можем просто взять первую половину результатов permutations(n-1, n-1) и добавить n. Это легко увидеть для n = 5.

Я предлагаю использовать следующий подход:

1. Мы устанавливаем, чтобы первый элемент всегда был 1. Таким образом, мы гарантируем, что возьмем только 1 перестановку для каждого набора эквивалентных перестановок. Это в основном то же самое, что вы сделали, сделав 4 всегда быть последним элементом в вашем примере.
2. Рассмотрим только такие перестановки, для которых элемент #2 меньше элемента #n. Для каждой перестановки в наборе, описанном первым правилом, будет одна и только одна перестановка, обратная ей. Таким образом, мы обязательно берем только одну перестановку для каждой такой пары.

И это алгоритм, который мы собираемся использовать для построения такого набора перестановок:

1. Найдите все пары элементов #2 и #n, где #2 меньше #n. Это combinations(n-1, 2, v = 2:n) .
2. Для каждой такой комбинации найдите все перестановки всех остальных n-3 элементов. Вот permutations(n - 3, n - 3, v = rest_elements) где rest_elements находится вектор со списком всех n-3 элементов, которые остаются, когда мы удаляем 1, #2 и #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
 

^{Создано 2021-08-28 пакетом reprex (v2.0.1)}