algorithm - una - distribucion uniforme youtube
¿Cómo genero una partición entera aleatoria uniforme? (7)
Una búsqueda en Google revela mucho sobre cómo generar todas las particiones posibles de un entero n en m partes, pero no he encontrado nada sobre muestrear una partición aleatoria de n distribuidas uniformemente en m partes.
Aquí hay un código que lo hace. Esto es O ( n 2 ) la primera vez que lo llama, pero crea un caché para que las llamadas posteriores sean O ( n ).
import random
cache = {}
def count_partitions(n, limit):
if n == 0:
return 1
if (n, limit) in cache:
return cache[n, limit]
x = cache[n, limit] = sum(count_partitions(n-k, k) for k in range(1, min(limit, n) + 1))
return x
def random_partition(n):
a = []
limit = n
total = count_partitions(n, limit)
which = random.randrange(total)
while n:
for k in range(1, min(limit, n) + 1):
count = count_partitions(n-k, k)
if which < count:
break
which -= count
a.append(k)
limit = k
n -= k
return a
Cómo funciona esto: podemos calcular cuántas particiones de un entero n hay en O ( n 2 ) de tiempo. Como efecto secundario, esto produce una tabla de tamaño O ( n 2 ) que luego podemos usar para generar la partición k th de n , para cualquier entero k , en tiempo O ( n ).
Entonces, total = el número de particiones. Elija un número aleatorio k de 0 a total - 1. Genere la k ª partición.
Después de buscar en Google, encontré un algoritmo para esto en el "Manual de Algoritmos Aplicados", que Google Books ha indexado . El algoritmo se encuentra en la sección 1.12.2, en la página 31.
El título de este post es un poco engañoso. Una partición entera aleatoria no está restringida por defecto, lo que significa que puede tener tantas partes de cualquier tamaño. La pregunta específica que se hace es sobre las particiones de n en m partes, que es un tipo de partición de entero restringido.
Para generar particiones enteras no restringidas, un algoritmo muy rápido y simple se debe a Fristedt, en un artículo llamado La estructura de particiones aleatorias de enteros grandes (1993) . El algoritmo es como sigue:
- Establecer x = exp (-pi / sqrt (6n)).
- Genere variables aleatorias independientes Z (1), Z (2), ..., Z (n), donde Z (i) se distribuye geométricamente con el parámetro 1-x ^ i.
- IF suma i * Z (i) = n, donde la suma se toma sobre todo i = 1,2, ..., n, luego STOP.
ELSE, repite 2.
Una vez que el algoritmo se detiene, entonces Z (1) es el número de 1s , Z (2) es el número de 2s , etc., en una partición elegida uniformemente al azar. La probabilidad de aceptar un conjunto de Z elegido al azar es asintóticamente 1 / (94n ^ 3) ^ (1/4), lo que significa que uno esperaría ejecutar este algoritmo O (n ^ (3/4)) veces antes de aceptar un solo muestra.
La razón por la que me tomé el tiempo para explicar este algoritmo es porque se aplica directamente al problema de generar una partición de n en exactamente m partes. Primero observa que
El número de particiones de n en exactamente m partes es igual al número de particiones de n con la parte más grande igual a m.
Entonces podemos aplicar el algoritmo de Fristedt directamente, pero en lugar de generar Z (1), Z (2), ..., Z (n), podemos generar Z (1), Z (2), ..., Z ( m-1), Z (m) +1 (el +1 aquí garantiza que la parte más grande es exactamente m, y 1 + Z (m) es igual en distribución a Z (m) condicional a Z (m)> = 1 ) y establezca el resto de Z (m + 1), Z (m + 2), ... igual a 0. Luego, una vez que obtengamos la suma objetivo en el paso 3, también tenemos la garantía de tener una muestra imparcial. Para obtener una partición de n en exactamente m partes, simplemente tome el conjugado de la partición generada.
La ventaja que esto tiene sobre el método recursivo de Nijenhuis y Wilf es que no hay requisitos de memoria que no sean almacenar las variables aleatorias Z (1), Z (2), etc. Además, el valor de x puede estar entre 0 y 1 y este algoritmo sigue siendo imparcial! Sin embargo, elegir un buen valor de x puede hacer que el algoritmo sea mucho más rápido, aunque la elección en el Paso 1 es casi óptima para particiones de enteros no restringidos.
Si n es realmente enorme y el algoritmo de Fristedt toma demasiado tiempo (y los métodos de tabla están fuera de discusión), existen otras opciones, pero son un poco más complicadas; vea mi tesis https://sites.google.com/site/stephendesalvo/home/papers para obtener más información sobre la división y conquista probabilística y sus aplicaciones.
He implementado la solución anterior y encontré que funciona muy bien si uno quiere calcular particiones enteras para n pero no con respecto a m. Si se trabaja con n grande, es posible que los límites de recursión y las pilas de llamadas deban aumentarse mucho.
Sin embargo, no necesita la primera función porque count_partitions (n, limit) en realidad será igual al número de particiones de ''n + limit'' con el ''límite'' de partes. Algunos programas matemáticos tienen funciones muy rápidas para encontrar el número de particiones de n en m partes.
Recientemente he derivado un método sin sesgos, muy simple y muy rápido (que usa memoization) para resolver su pregunta exacta : ¿ Un algoritmo para generar aleatoriamente particiones enteras de una longitud particular, en Python?
Se basa en saber algo sobre particiones ordenadas léxicamente de n que tienen m partes y utiliza un enfoque similar a los algoritmos bien aceptados (por ejemplo, Nijenhuis y Wilf 1978) que encuentran particiones aleatorias de n, y es conceptualmente similar a la anterior.
En resumen, si hay x particiones de n con m partes, entonces elegimos un número aleatorio entre 1 y x. Ese número aleatorio se codificará para una y solo una partición que satisfaga n y m. Espero que esto ayude.
Otro algoritmo de los algoritmos combinatorios página 52, "Generación aleatoria de n en k partes"
- Elija
a1,a2, ..,ak-1un subconjunto aleatorio dek-1de{1,2,..,n+k-1}(ver más abajo 1., 2.) - Set
r1=a1-1;rj=aj-aj-1-1(j=2..k-1);rk= n+k-1-ak-1 - Los
rj(j=1..k) constituyen la partición aleatoria denenkpartes
Este algoritmo para composiciones aleatorias se basa en el modelo de "bolas en celdas".
Brevemente elegimos las posiciones de los límites de las celdas al azar, luego, por diferencia, descubrimos cuántas bolas hay en cada celda.
Para generar de manera eficiente un subconjunto aleatorio de un conjunto, vea 1. respuesta relacionada aquí y 2. here
actualizar
Otro enfoque que utiliza un solo número aleatorio en [0,1] para generar de manera uniforme una partición aleatoria (también llamada composición) se presenta en IVAN STOJMENOVIC, "GENERACIÓN ALEATORIA ALEATORIA Y ADAPTATIVA DE OBJETOS COMBINATORIOS" (sección 5, sección 10)
Sólo una versión más en c #.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication6
{
class Program
{
static Random random = new Random();
static void Main(string[] args)
{
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
Console.ReadKey();
}
static int[] GetUniformPartition(int input, int parts)
{
if(input<= 0 || parts <= 0)
throw new ArgumentException("invalid input or parts");
if (input < MinUniformPartition(parts))
throw new ArgumentException("input is to small");
int[] partition = new int[parts];
int sum = 0;
for (int i = 0; i < parts-1; i++)
{
int max = input - MinUniformPartition(parts - i - 1) - sum;
partition[i] = random.Next(parts - i, max);
sum += partition[i];
}
partition[parts - 1] = input - sum; // last
return partition;
}
// sum of 1,2,3,4,..,n
static int MinUniformPartition(int n)
{
return n * n - 1;
}
static void PrintPartition(int[] p)
{
for (int i = 0; i < p.Length; i++)
{
Console.Write("{0},", p[i]);
}
Console.WriteLine();
}
}
}
Este código producirá la siguiente salida:
5,8,7,2,2,
6,6,7,2,3,
5,7,6,2,4,
6,4,3,2,9,
7,8,4,4,1,
Tengo un generador de partición distribuido uniformemente.
Donde n: = el entero a particionar, r: = el número de segmentos: El algoritmo es una versión parcheada del método ingenuo de simplemente insertar particiones al azar. El problema con este método, como me pareció cuando miré su salida, fue que es menos probable que ocurran escenarios en los que las particiones se colocan en el mismo lugar. Solo hay una forma de obtener {1,1,1}, mientras que hay 3! las formas de obtener {2,4,9}, cualquiera de {4,2,9}, {2,4,9}, {9,4,2} ... llevarán a la misma ubicación de partición cuando se clasifiquen. Esto ha sido modificado proporcionando oportunidades explícitas adicionales para las repeticiones. Para cada inserción de partición, existe la posibilidad de que la posición de la partición no sea aleatoria, pero se seleccionará como una repetición de un valor anteriormente seleccionado. Esto equilibra la distribución de probabilidad desigual del método ingenuo desde el principio.
He demostrado por agotamiento que cada partición es perfectamente igual de probable para r = 3, n = 2. Lo compruebo para valores más altos, pero las empresas de buen corazón para hacerlo solo encontraron signos prometedores. También lo probé en una entrada aleatoria, encontrando que es al menos aproximadamente igual para todos los valores que probé [pero probablemente perfectamente parejo].
Aquí está en C ++ 11: [el formato de salida es diferente de lo que estás esperando, son las posiciones de las particiones en lugar del tamaño del espacio entre ellas. La conversión es fácil, sin embargo]
#include <vector>
#include <algorithm>
#include <random>
#include <cassert>
template <typename Parting, typename Seed>
vector<Parting> partitionGen(unsigned nparts, unsigned bandw, Seed seed){//nparts is the number of parts, that is, one greater than the number of dividers listed in the output vector. Bandw is the integer being partitioned.
assert(nparts > 0);
vector<Parting> out(nparts-1);
srand(seed);
unsigned genRange = bandw;
for(auto i=out.begin(); i<out.end(); ++i, ++genRange){
unsigned gen = rand()%genRange;
*i = ((gen<bandw)?
gen:
*(i-(gen-bandw+1)));
}
sort(out.begin(), out.end(), less<Parting>());
return out;
}
Aunque no me gusta el hecho de que tengo que arreglarlo. Si la versión de Vlody tiene una distribución uniforme, parece que sería mejor.