Permutaciones alternas aleatorias

Question

Un permutación alternada de {1, ..., n} es uno donde (1) > (2) < (3) > (4) < ... Por ejemplo: (24153) es una permutación alterna de longitud 5.

Si $E_n$ es el número de permutaciones alternas de longitud n, el $\sec x + \tan x = \sum_{n \geq 0} E_n \frac{x^n}{n!}$ es la función generadora exponencial.

¿Cómo se muestrean las permutaciones alternas de manera uniforme y aleatoria? El muestreo de rechazo se volvería rápidamente ineficaz, ya que $\frac{E_n}{n!} \approx \frac{4}{\pi} \left(\frac{2}{\pi} \right)^n$ decae exponencialmente en n .

Answer 1

Editar: en versiones anteriores de este post afirmé que el algoritmo de abajo generaba permutaciones alternas aleatorias con probabilidad uniforme. Eso no es cierto, me disculpo por no haberlo comprobado antes de publicar. Todavía no conozco una forma sencilla de generarlas con probabilidad uniforme.

Comience con una lista vacía L. Los lugares de la lista están numerados del 1 al n, y la inserción de un nuevo elemento en el lugar j-ésimo significa que los elementos en los lugares j hasta el final de la lista se empujan un lugar a la derecha. Entonces, al final del siguiente algoritmo L contendrá una permutación aleatoria alternada en L, pero no con probabilidad uniforme. La entrada es n, la longitud de la permutación.

set j <- 0
set k <- 1
loop
  set j <- random integer in the interval [j+1, k]
  insert k into the list L at the j-th place
  if k = n exit loop
  k <- k+1
  set j <- random integer in the  interval [1, j]
  insert k into the list L at the j-th place
  if k = n exit loop
  k <- k+1
end loop

Para la lista se puede utilizar una lista enlazada o un árbol de búsqueda binario equilibrado en el que cada nodo contiene el tamaño de su subárbol. La primera es más fácil de codificar pero se ejecuta en O(n^2), la segunda es más complicada de codificar, pero se ejecuta en O(n log n).

Editar: Aquí hay una implementación más concreta en C++, utilizando una lista enlazada (estoy utilizando el generador de números aleatorios de lujo, es posible que tenga que utilizar gcc 4.2 o posterior)

#include <list>
#include <tr1/random>

using namespace std;
using namespace std::tr1;

list<int> random_alt_perm(int n) {
    variate_generator<mt19937, uniform_real<> > urng(mt19937(time(NULL)), uniform_real<>());
    list<int> l;
    for (int k=1, j=0; k<=n; ++k) {
        double rnd=urng();
        if (k&1) j = j + 1 + (k-j)*rnd;
        else j = 1 + j*rnd;
        list<int>::iterator it=l.begin();
        advance(it, j-1);
        l.insert(it, k);
    }
    return l;
}