R: первое N из всех перестановок

Question

Я ищу функцию, которая

• может перечислить все n! перестановки заданного входного вектора (обычно это просто последовательность 1:n)
• может также перечислить только первое N из всех n! Перестановки

Первое требование удовлетворяется, например, permn() из пакета combinat, permutations() из пакета e1071 или permutations() из пакета gtools. Тем не менее, я уверен, что есть еще одна функция из некоторого пакета, которая также предоставляет вторую функцию. Я использовал его один раз, но с тех пор забыл его имя.

Edit: Определение «first N» является произвольным: функция просто нуждается во внутренней схеме перечисления, которая всегда соблюдается и должна прерваться после вычисления N перестановок.

Как правильно заметил Spacedman, крайне важно, чтобы функция не вычисляла больше перестановок, чем фактически необходимо (для экономии времени).

Edit - решение: я вспомнил, что я использовал, это было numperm() из пакета sna. numperm(4, 7) дает 7-ю перестановку элементов 1:4, для первого N нужно цикл.

Answer 1

Кажется, что лучший способ приблизиться к этому - создать итератор , который мог бы создавать список перестановок, вместо использования функции, подобной permn, которая генерирует весь список заранее (дорогой операция).

Отличным местом для поиска рекомендаций по созданию таких объектов является модуль itertools в стандартной библиотеке Python. Itertools был частично повторно реализован для R как пакет с тем же именем .

Ниже приведен пример, который использует itertools R для реализации порта генератора Python, который создает итераторы для перестановок:

require(itertools)

permutations <- function(iterable) {
  # Returns permutations of iterable. Based on code given in the documentation
  # of the `permutation` function in the Python itertools module:
  #   http://docs.python.org/library/itertools.html#itertools.permutations
  n <- length(iterable)
  indicies <- seq(n)
  cycles <- rev(indicies)
  stop_iteration <- FALSE

  nextEl <- function(){
    if (stop_iteration){ stop('StopIteration', call. = FALSE) }
    if (cycles[1] == 1){ stop_iteration <<- TRUE } # Triggered on last iteration

    for (i in rev(seq(n))) {
      cycles[i] <<- cycles[i] - 1
      if ( cycles[i] == 0 ){
        if (i < n){
          indicies[i:n] <<- c(indicies[(i+1):n], indicies[i])
        }
        cycles[i] <<- n - i + 1
      }else{
        j <- cycles[i]
        indicies[c(i, n-j+1)] <<- c(indicies[n-j+1], indicies[i])
        return( iterable[indicies] )
      }
    }
  }

  # chain is used to return a copy of the original sequence 
  # before returning permutations. 
  return( chain(list(iterable), new_iterator(nextElem = nextEl)) )

}

Чтобы неправильно цитировать Кнут : «Остерегайтесь ошибок в приведенном выше коде; я только пробовал, но не доказал, что это правильно».

За первые 3 перестановки последовательности 1:10, permn платит высокую цену за вычисление ненужных перестановок:

> system.time( first_three <- permn(1:10)[1:3] )
   user  system elapsed 
134.809   0.439 135.251 
> first_three
[[1]]
 [1]  1  2  3  4  5  6  7  8  9 10

[[2]]
 [1]  1  2  3  4  5  6  7  8 10  9

[[3]]
 [1]  1  2  3  4  5  6  7 10  8  9)

Однако итератор, возвращаемый permutations, может быть запрошен только для первых трех элементов, что экономит много вычислений:

> system.time( first_three <- as.list(ilimit(permutations(1:10), 3)) )
   user  system elapsed 
  0.002   0.000   0.002 
> first_three
[[1]]
 [1]  1  2  3  4  5  6  7  8  9 10

[[2]]
 [1]  1  2  3  4  5  6  7  8 10  9

[[3]]
 [1]  1  2  3  4  5  6  7  9  8 10

Алгоритм Python генерирует перестановки в другом порядке, чем permn.

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

> system.time( all_perms <- as.list(permutations(1:10)) )
   user  system elapsed 
498.601   0.672 499.284

Хотя он намного дороже, поскольку алгоритм Python интенсивно использует циклы по сравнению с permn. Python фактически реализует этот алгоритм в C, который компенсирует неэффективность интерпретируемых циклов.

Код доступен в гисте на GitHub . Если у кого есть идея получше, раскошелиться!

Answer 2

В моей версии R / combinat функция permn() имеет длину чуть более тридцати строк.Одним из способов было бы сделать копию permn и изменить ее, чтобы остановить раньше.