Un algoritmo per la generazione casuale di partizioni intere di una lunghezza particolare, in Python?

Question

Utilizzo la funzione random_element() fornita da SAGE per generare partizioni intere casuali per un dato numero intero (N) di lunghezza particolare (S). Sto cercando di generare campioni casuali imparziali dal set di tutte le partizioni per i valori dati di N e S. La funzione SAGE restituisce rapidamente partizioni casuali per N (ad esempio Partitions(N).random_element()).

Tuttavia, rallenta immensamente quando si aggiunge S (ad esempio Partitions(N,length=S).random_element()). Allo stesso modo, il filtraggio delle partizioni casuali di N di lunghezza pari a S è incredibilmente lento.

Tuttavia, e spero che questo aiuta qualcuno, ho trovato che nel caso in cui la funzione restituisce una partizione di N che non corrisponde alla lunghezza S, che la partizione coniugato è spesso di lunghezza S. Cioè:

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

Questo aumenta la velocità di partizioni lunghezza S si trovano e sembra produrre campioni imparziali (ho esaminato i risultati contro interi set di partizioni per vari valori di N e S).

Tuttavia, sto utilizzando i valori di N (ad esempio 10,000) e S (ad esempio 300) che rendono questo approccio persino lento. Il commento associato alla funzione random_element() di SAGE ammette che c'è molto spazio per l'ottimizzazione. Quindi, esiste un modo per generare più rapidamente campioni imparziali (ad esempio casuali) di partizioni intere corrispondenti ai valori dati di N e S, forse, non generando partizioni che non corrispondono a S? Inoltre, l'uso delle partizioni coniugate funziona bene in molti casi per produrre campioni imparziali, ma non posso dire di aver capito esattamente perché.

Answer 1

Infine, ho un definitivo metodo imparziale che ha un tasso di rifiuto zero. Certo, l'ho testato per assicurarmi che i risultati siano campioni rappresentativi di interi set fattibili. È molto veloce e totalmente imparziale. Godere.

from sage.all import * 
import random 

In primo luogo, una funzione per trovare il più piccolo addendo massimo per una partizione di n con s parti

def min_max(n,s): 

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

    return _min 

Avanti, una funzione che utilizza una cache e memoiziation per trovare il numero di partizioni di n con s parti aventi x come la parte più grande. Questo è veloce, ma penso che ci sia una soluzione più elegante da avere. ad esempio, spesso: P (N, S, max = K) = P (NK, S-1) Grazie a ante (https://stackoverflow.com/users/494076/ante) per avermi aiutato con questo: 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)] 

Infine, un funzione per trovare partizioni casuali uniformi di n con s parti, senza tasso di rifiuto! Ogni codice numerico scelto a caso per una partizione specifica di n avente s parti.

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

approccio semplice: assegnare casualmente i numeri interi:

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

Answer 3

mi sono imbattuto in un problema simile quando stavo cercando di calcolare la probabilità dei forti problemi di compleanno.

Prima di tutto, la funzione di partizione esplode quando viene fornita solo una modica quantità di numeri. Restituirai MOLTE informazioni. Indipendentemente dal metodo che usi N = 10000 e S = 300 genererai quantità ridicole di dati. Sarà lento. È probabile che qualsiasi implementazione di Python pura sia altrettanto lenta o più lenta. Cerca di creare un CModule.

Se si vuole provare Python l'approccio che ho preso come una combinazione di itertools e generatori per mantenere l'utilizzo della memoria verso il basso. Non mi sembra di avere il mio codice a portata di mano più, ma qui è un buon impementation:

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

EDIT:

Trovato il mio codice:

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