पाइथन में, किसी विशेष लंबाई के अनियमित विभाजन को यादृच्छिक रूप से उत्पन्न करने के लिए एक एल्गोरिदम?

Question

मैं एक दिया पूर्णांक (N) है कि एक विशेष लंबाई (S) कर रहे हैं के लिए यादृच्छिक पूर्णांक विभाजन उत्पन्न करने के लिए सेज द्वारा प्रदान की random_element() फ़ंक्शन का उपयोग किया गया है। मैं N और S के दिए गए मानों के लिए सभी विभाजनों के सेट से निष्पक्ष यादृच्छिक नमूने उत्पन्न करने की कोशिश कर रहा हूं। एसएजी का कार्य जल्दी से एन (यानी Partitions(N).random_element()) के लिए यादृच्छिक विभाजन देता है।

हालांकि, S (यानी Partitions(N,length=S).random_element()) जोड़ते समय यह बहुत धीमा हो जाता है। इसी प्रकार, N के यादृच्छिक विभाजन को फ़िल्टर करना जो लंबाई S है, अविश्वसनीय रूप से धीमा है।

हालांकि, और मुझे आशा है कि यह किसी को मदद मिलती है, मैंने पाया मामले में फ़ंक्शन कि जब N के विभाजन लंबाई 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 के विभाजन पाया और निष्पक्ष नमूने का उत्पादन करने के लिए प्रकट होता है कर रहे हैं बढ़ जाती है (मैं N और S के विभिन्न मूल्यों के लिए विभाजन की पूरी सेट के खिलाफ परिणामों की जांच की है)।

हालांकि, मैं एन (उदा। 10,000) और एस (उदा। 300) के मानों का उपयोग कर रहा हूं जो इस दृष्टिकोण को अव्यवहारिक रूप से धीमा कर देते हैं। SAGE के random_element() फ़ंक्शन से जुड़ी टिप्पणी मानती है कि अनुकूलन के लिए बहुत सारे कमरे हैं। तो, वहाँ एक रास्ता और अधिक तेजी से निष्पक्ष (अर्थात यादृच्छिक वर्दी) दिया N और S, शायद के मूल्यों पूर्णांक विभाजन मिलान के नमूने उत्पन्न करने के लिए, विभाजन कि S मेल नहीं खाते नहीं पैदा कर कर रहा है? इसके अतिरिक्त, संयुग्मित विभाजन का उपयोग निष्पक्ष नमूनों का उत्पादन करने के लिए कई मामलों में अच्छी तरह से काम करता है, लेकिन मैं यह नहीं कह सकता कि मैं समझता हूं कि क्यों।

Answer 1

अंत में, मैं एक निश्चित राशि निष्पक्ष विधि जिसमें शून्य अस्वीकृति दर है। बेशक, मैंने यह सुनिश्चित करने के लिए परीक्षण किया है कि परिणाम पूरे व्यवहार्य सेट के प्रतिनिधि नमूने हैं। यह बहुत तेज़ और पूरी तरह से निष्पक्ष है। का आनंद लें।

from sage.all import * 
import random 

सबसे पहले, एक समारोह रों भागों

def min_max(n,s): 

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

    return _min 

इसके बाद, की संख्या को खोजने के लिए एक कैश और memoiziation का उपयोग करता है एक समारोह के साथ n के एक विभाजन के लिए छोटी से छोटी अधिकतम योज्य को खोजने के लिए भाग एन के हिस्सों के साथ x को सबसे बड़ा हिस्सा है। यह तेज़ है, लेकिन मुझे लगता है कि एक और अधिक सुरुचिपूर्ण समाधान था। जैसे, अक्सर: पी (एन, एस, अधिकतम = कश्मीर) = पी (एन.के., एस 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)] 

अंत में , एक बिना किसी अस्वीकृति दर के, एस भागों के साथ एन के समान यादृच्छिक विभाजन खोजने के लिए कार्य! एन के हिस्सों के विशिष्ट विभाजन के लिए प्रत्येक यादृच्छिक रूप से चुने गए नंबर कोड।

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

मैं जब मैं मजबूत जन्मदिन समस्या की संभावना की गणना करने के कोशिश कर रहा था एक ऐसी ही समस्या हुई थी।

पहले, विभाजन समारोह फट जब संख्या का केवल मामूली अवधि दी गयी है। आप बहुत सारी जानकारी लौट रहे होंगे। कोई फर्क नहीं पड़ता कि आप किस विधि का उपयोग कर रहे हैं एन = 10000 और एस = 300 डेटा की हास्यास्पद मात्रा उत्पन्न करेगा। यह धीमा हो जाएगा। संभावना है कि आप जिस शुद्ध पायथन कार्यान्वयन का उपयोग करते हैं वह उतना ही धीमा या धीमा होगा। एक सीएमओडी बनाने के लिए देखो।

आप दृष्टिकोण मैं 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