在Python中隨機生成特定長度的整數分區的算法？

Question

我一直在使用SAGE提供的random_element()函數來爲給定整數（N）生成隨機整數分區，它們是特定長度的（S）。我試圖從給定值爲N和S的所有分區集合中生成無偏差的隨機樣本。 SAGE的功能可快速返回N個隨機分區（即Partitions(N).random_element()）。

但是，當添加S（即Partitions(N,length=S).random_element()）時，它會非常緩慢。同樣，篩選長度爲S的N的隨機分區速度非常慢。

不過，我希望這可以幫助別人，我發現，在該情況下，當函數返回的N分區不匹配長度S，使共軛物分區往往是長S.即是：

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

這增加了長度的S分區被發現，並且似乎產生無偏採樣速率（I已經研究針對爲N和S各種值分區的整個組的結果）。然而，我使用N的值（例如10,000）和S（例如300），這使得即使這種方法實際上也很慢。與SAGE的random_element()函數相關的評論承認有充足的優化空間。那麼，是否有辦法更快速地生成匹配給定值N和S的整數分區的無偏（即隨機均勻）樣本，或許不會生成不匹配S的分區？此外，使用共軛分區在很多情況下都能很好地生成無偏差的樣本，但我不能說我準確地理解了原因。

Answer 1

最後，我有一個明確無偏方法具有零拒絕率。當然，我已經對它進行了測試，以確保結果是整個可行集的代表性樣本。它非常快速且完全沒有偏見。請享用。

from sage.all import * 
import random 

首先，一個函數來找到對於n的與S份

def min_max(n,s): 

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

    return _min 

接着，使用高速緩存和memoiziation找到的數目的功能的分區中的最小的最大加數n的分區 ，其中s的部分以x爲最大部分。這很快，但我認爲 是一個更優雅的解決方案。例如，通常：P（N，S，最大= K）= P（NK，S-1） 由於賭注（https://stackoverflow.com/users/494076/ante）幫我與此： 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)] 

最後，函數可以找到n個具有s個部分的統一的隨機分區，而且沒有拒絕率！每個隨機選擇的數字編碼具有n個部分的n的特定分區。

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

簡單的方法：隨機分配的整數：

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

Answer 3

我遇到了類似的問題，當我試圖計算出強烈的生日問題的可能性。

首先，分區功能在僅給予適量的數字時爆炸。你將會返回大量的信息。無論你使用哪種方法N = 10000和S = 300，都會產生荒謬的數據量。它會很慢。有可能你使用的任何純Python實現同樣緩慢或者更慢。期待制作一個CModule。

如果你想嘗試python作爲itertools和生成器的組合來保持內存使用量的方法。我似乎並沒有讓我的代碼方便了，但這裏有一個很好的impementation：

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

編輯：

找到我的代碼：

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