R: N primera de todas las permutaciones

Question

estoy en busca de una función que

• puede enumerar todos los n! las permutaciones de un vector de entrada dado (típicamente solo la secuencia 1:n)
• también pueden enumerar solo la primera N de todas las n! permutaciones

El primer requisito se cumple, por ejemplo, por permn() de paquete combinat, permutations() de paquete e1071, o permutations() de paquete gtools. Sin embargo, estoy seguro de que hay otra función de algún paquete que también proporciona la segunda función. Lo usé una vez, pero desde entonces he olvidado su nombre.

Edit: La definición de "first N" es arbitraria: la función solo necesita un esquema de enumeración interna que siempre se sigue, y debe romperse después de que se calculan las permutaciones de N.

Como Spacedman señaló correctamente, es crucial que la función no calcule más permutaciones de las realmente necesarias (para ahorrar tiempo).

Edición - solución: Recordé lo que estaba usando, era numperm() del paquete sna. numperm(4, 7) da la séptima permutación de los elementos 1:4, para la primera N, hay que hacer un ciclo.

Answer 1

Parece que la mejor manera de abordar esto sería construir un iterador que podría producir la lista de permutaciones en lugar de utilizar una función como permn que genera toda la lista en la delantera (una operación costosa).

Un excelente lugar para buscar orientación sobre la construcción de dichos objetos es el módulo itertools en la biblioteca estándar de Python. Itertools se ha vuelto a implementar parcialmente para R como a package of the same name.

El siguiente es un ejemplo que utiliza itertools de R para poner en práctica un puerto del generador de Python que crea iteradores de permutaciones:

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))) 

} 

Para citar incorrectamente Knuth: "Cuidado con los errores en el código anterior; Solo lo he probado, no he probado que sea correcto."

Para los 3 primeros permutaciones de la secuencia 1:10, permn paga un precio muy alto para el cálculo de permutaciones innecesarios:

> 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) 

Sin embargo, el iterador devuelto por permutations puede ser consultada por sólo los tres primeros elementos que ahorran una gran cantidad de cálculos:

> 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 

El algoritmo de Python genera permuta ciones en un orden diferente que permn.

Informática todas las permutaciones es todavía posible:

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

Aunque mucho más caro que el algoritmo de Python hace un uso intensivo de los bucles en comparación con permn. Python realmente implementa este algoritmo en C que compensa la ineficiencia de los bucles interpretados.

El código está disponible in a gist on GitHub. Si alguien tiene una idea mejor, ¡bájate!

Answer 2

En mi versión de R/combinat, la función permn() tiene más de treinta líneas de longitud. Una forma sería hacer una copia de permn y cambiarla para detenerla antes.