Una búsqueda en Google revela mucho acerca de la generación de todas las particiones posibles de un entero n en m partes, pero no he encontrado nada sobre el muestreo de una partición aleatoria uniformemente distribuida de n en m partes.¿Cómo puedo generar una partición entera aleatoria uniforme?
Aquí hay un código que lo hace. Esta es O (n) la primera vez que la llamas, pero crea una memoria 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 el número de particiones de un entero n existen en O (n ) tiempo. Como efecto secundario, esto produce una tabla de tamaño O (n) que luego puede utilizar para generar el k º partición de n, para cualquier entero k, en O (n) tiempo.
Así que deje total = el número de particiones. Elija un número aleatorio k de 0 a total - 1. Genere la partición k th.
Entonces count_partitions (n, limit) cuenta el número de particiones de n en partes inferiores o iguales al límite. Está bien, veo cómo estás contando eso. Y luego, dado un bijection entre los enteros 1, ..., count_partitions (n, n) y las particiones de n, random_partition elige uno de esos enteros y construye la partición correspondiente. Por supuesto, esta solución no aborda la cuestión, que solicitó una partición aleatoria de n * en exactamente m partes *. Supongo que debería haber dejado eso en claro en el título. Sin embargo, definitivamente puedo encontrar lo que necesito en base a esto. – cdf
Oh, lo siento. ¡Leí mal la pregunta! De todos modos, todo lo que hice fue tomar un código que ya tenía para generar todas las particiones, hacer dos copias y convertir una copia en la función de conteo y la otra copia en la función kth-partition-constructing. El mismo enfoque exacto debería funcionar para su problema. –
¡Uy! Nunca llegó a marcar esto como respondido. Lo siento por eso. – cdf
Después de buscar en Google encontré un algoritmo para esto en el "Manual de algoritmos aplicados", which Google Books has indexed. El algoritmo se proporciona en la sección 1.12.2, en la página 31.
Sí, me encontré con eso, también. No genera particiones con exactamente m partes, y asume que ya se ha calculado RP (n, m) (equivalente a count_partitions de Jason (n, limit), con limit = m). Estoy pensando que hay que trabajar menos para calcular el número de particiones de n en m partes. – cdf
Solo 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 próxima 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,
He implementado la solución anterior y se encontró que funciona muy bien si uno quiere calcular las particiones enteros para n, pero no con respecto a m. Si se trabaja con n grande, puede ser necesario aumentar mucho los límites de recursividad y las pilas de llamadas.
Sin embargo, no necesita la primera función porque count_partitions (n, limit) realmente equivaldrá al número de particiones de 'n + limit' con 'limit' number of parts. Algunos programas matemáticos tienen funciones muy rápidas para encontrar el número de partición de n en m partes.
he obtenido recientemente un método sin duda no sesgada, muy simple y muy rápida (usando memoization) para resolver su pregunta exacta: An algorithm for randomly generating integer partitions of a particular length, in Python?
Se basa en saber algo acerca de las particiones léxico ordenada de n tiene m piezas 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 al 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 codificará para una y solo una partición que satisfaga n y m. Espero que esto ayude.
Tengo un generador de particiones distribuido uniformemente.
Donde n: = el número entero a particionar, r: = el número de sectores: El algoritmo es una versión parcheada del método ingenuo de simplemente insertar separaciones al azar. El problema con este método, como me pareció cuando mire su resultado, fue que es menos probable que ocurran escenarios donde las separaciones 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 enmendado al proporcionar oportunidades explícitas adicionales para repeticiones. Para cada inserción de partición, existe la posibilidad de que la posición de la partición no sea aleatoria, sino que se seleccionará como una repetición de un valor anteriormente seleccionado. Esto equilibra la distribución de probabilidad desigual del método ingenuo.
He comprobado por agotamiento que cada partición es perfectamente posible para r = 3, n = 2. Lo comprobé para valores más altos, pero las empresas sin corazón para hacerlo solo encontraron señales prometedoras. También lo probé con entradas aleatorias, y descubrí que es al menos más o menos para todos los valores que probé [pero probablemente perfectamente].
aquí está en C++ 11: [el formato de salida es diferente de lo que está esperando, es la posición de las separaciones 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;
}
no me gusta el hecho de que tengo que solucionar el problema sin embargo. Si la versión de Vlody tiene una distribución uniforme, parece que sería mejor.
El título de esta publicación es un poco engañoso. Una partición entera aleatoria es por defecto sin restricciones, lo que significa que puede tener tantas partes de cualquier tamaño. La pregunta específica es acerca de las particiones de n en m partes, que es un tipo de partición de entero restringido.
Para generar particiones de enteros de libre disposición, un algoritmo muy rápido y simple es debido a Fristedt, en un artículo llamado La estructura de azar particiones de grandes Entero (1993). El algoritmo es el siguiente:
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 elegido 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 aplica directamente al problema de generar una partición de n en exactamente m partes. Primero, observe 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í asegura que la parte más grande es exactamente m, y 1 + Z (m) es igual en distribución a Z (m) condicional en Z (m)> = 1) y establece todos los demás Z (m + 1), Z (m + 2), ... igual a 0. Entonces, una vez que obtenemos la suma objetivo en el paso 3, también garantizamos 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 además de almacenar las variables aleatorias Z (1), Z (2), etc. Además, el valor de x puede ser cualquier cosa 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 las particiones enteras sin restricciones.
Si n es realmente enorme y el algoritmo de Fristedt lleva demasiado tiempo (y los métodos de tabla están fuera de discusión), existen otras opciones, pero son un poco más complicadas; ver mi tesis https://sites.google.com/site/stephendesalvo/home/papers para más información sobre dividebilidad y conquista probabilística y sus aplicaciones.
explicación muy agradable, +1 –
Otro algoritmo de Combinatorial Algorithms la página 52, "Random Generación de n en k partes"
a1, a2, .., ak-1 una al azar k-1 subconjunto de {1,2,..,n+k-1} (ver a continuación 1., 2.)r1=a1-1; rj=aj-aj-1-1 (j=2..k-1); rk= n+k-1-ak-1rj (j=1..k) constituyen la partición aleatoria de n en k partesEste algoritmo para composiciones aleatorias se basa en la " bolas en modelo de células.
En pocas palabras, elegimos las posiciones de los límites de la celda al azar, y luego, al diferenciar, encontramos cuántas bolas hay en cada celda.
Para generar de manera eficiente un subconjunto al azar de un conjunto, ver una actualización 1. related answer here y 2. here
Otro enfoque utilizando un solo número aleatorio en [0,1] para generar uniformemente un azar partición (también llamada composición) se da en IVAN STOJMENOVIC, "ON RANDOM AND ADAPTIVE PARALLEL GENERATION OF COMBINATORIAL OBJECTS" (sección 5, sección 10)
Tal vez me esté perdiendo algo. ¿Por qué no simplemente hacer m cortes distribuidos uniformemente (sobre los posibles puntos de corte posibles)? Es posible que pueda optimizar un poco, pero probablemente no mucho. – Beta
@Beta No tengo muy claro qué algoritmo estás sugiriendo. ¿Podría ser más específico? Además, de las posibles interpretaciones que se me ocurren para su sugerencia, algunas parecen dar como resultado una distribución uniforme, pero otras no. – PeterAllenWebb
opencover: para aclarar, se refiere a un algoritmo que es equivalente a (a) generar todas las particiones posibles; (b) elija uno al azar. Pero con suerte mucho más rápido. ¿Derecha? –