Algoritmo para generar aleatoriamente particiones enteras de una longitud determinada, en Python?

Question

He estado utilizando la función random_element() proporcionada por SAGE para generar particiones enteras aleatorias para un número entero dado (N) que tienen una longitud determinada (S). Intento generar muestras aleatorias imparciales del conjunto de todas las particiones para los valores dados de N y S. La función de SAGE devuelve rápidamente particiones aleatorias para N (es decir, Partitions(N).random_element()).

Sin embargo, se ralentiza enormemente al agregar S (es decir, Partitions(N,length=S).random_element()). Del mismo modo, el filtrado de particiones aleatorias de N que son de longitud S es increíblemente lento.

Sin embargo, y espero que esto ayude a alguien, me he dado cuenta que en el caso de que la función devuelve una partición de N que no coincida con la longitud S, que la partición conjugada es a menudo de longitud S. Es decir:

S = 10 
N = 100 
part = list(Partitions(N).random_element()) 
    if len(part) != S: 
     SAD = list(Partition(part).conjugate()) 
     if len(SAD) != S: 
      continue 

Esto aumenta la velocidad a la que se encuentran particiones de longitud S y aparece para producir muestras de recomendaciones (he examinado los resultados contra conjuntos completos de particiones para varios valores de N y S).

Sin embargo, estoy usando valores de N (por ejemplo, 10,000) y S (por ejemplo, 300) que hacen que incluso este enfoque sea poco práctico. El comentario asociado con la función random_element() de SAGE admite que hay mucho espacio para la optimización. Entonces, ¿hay alguna forma de generar más rápidamente muestras imparciales (es decir, aleatorio) de particiones enteras que coincidan con los valores dados de N y S, quizás, al no generar particiones que no coincidan con S? Además, el uso de particiones conjugadas funciona bien en muchos casos para producir muestras imparciales, pero no puedo decir que entiendo precisamente por qué.

Answer 1

Por último, tengo una manera definitiva método imparcial que tiene una tasa de rechazo cero. Por supuesto, lo he probado para asegurarme de que los resultados sean muestras representativas de conjuntos factibles completos. Es muy rápido y totalmente imparcial. Disfrutar.

from sage.all import * 
import random 

En primer lugar, una función para encontrar el sumando máximo más pequeño para una partición de n con s partes

def min_max(n,s): 

    _min = int(floor(float(n)/float(s))) 
    if int(n%s) > 0: 
     _min +=1 

    return _min 

A continuación, una función que utiliza una memoria caché y memoiziation para encontrar el número de particiones de n con s partes que tienen x como la parte más grande. Esto es rápido, pero creo que hay una solución más elegante. por ejemplo, a menudo: P (N, S, max = K) = P (NK, S-1) Gracias a ante (https://stackoverflow.com/users/494076/ante) para ayudar a mí con este: Finding the number of integer partitions given a total, a number of parts, and a maximum summand

D = {} 
def P(n,s,x): 
    if n > s*x or x <= 0: return 0 
    if n == s*x: return 1 
    if (n,s,x) not in D: 
     D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s)) 
    return D[(n,s,x)] 

Finalmente, una ¡Funciona para encontrar particiones aleatorias uniformes de n con s partes, sin tasa de rechazo! Cada número elegido al azar codifica para una partición específica de n que tiene s partes.

def random_partition(n,s): 
    S = s 
    partition = [] 
    _min = min_max(n,S) 
    _max = n-S+1 

    total = number_of_partitions(n,S) 
    which = random.randrange(1,total+1) # random number 

    while n: 
     for k in range(_min,_max+1): 
      count = P(n,S,k) 
      if count >= which: 
       count = P(n,S,k-1) 
       break 

     partition.append(k) 
     n -= k 
     if n == 0: break 
     S -= 1 
     which -= count 
     _min = min_max(n,S) 
     _max = k 

    return partition 

Answer 2

enfoque simple: asignar aleatoriamente los números enteros:

def random_partition(n, s): 
    partition = [0] * s 
    for x in range(n): 
     partition[random.randrange(s)] += 1 
    return partition 

Answer 3

me encontré con un problema similar cuando estaba tratando de calcular la probabilidad de que la fuerte problema cumpleaños.

En primer lugar, la función de partición explota cuando se le da solo una cantidad modesta de números. Volverás MUCHA información. No importa qué método estés usando N = 10000 y S = 300 generará cantidades ridículas de datos. Será lento. Es probable que cualquier implementación pura de Python que use sea igualmente lenta o lenta. Mira para hacer un CModule.

Si quiere probar Python, el enfoque lo tomé como una combinación de itertools y generadores para mantener el uso de la memoria. No parecen tener mi código a mano nunca más, pero aquí es una buena impementation:

http://wordaligned.org/articles/partitioning-with-python

EDIT:

encontrado mi código:

def partition(a, b=-1, limit=365): 
    if (b == -1): 
    b = a 
    if (a == 2 or a == 3): 
    if (b >= a and limit): 
     yield [a] 
    else: 
     return 
    elif (a > 3): 
    if (a <= b): 
     yield [a] 
    c = 0 
    if b > a-2: 
     c = a-2 
    else: 
     c = b 
    for i in xrange(c, 1, -1): 
     if (limit): 
     for j in partition(a-i, i, limit-1): 
      yield [i] + j