क्रमपरिवर्तन से बचना ओवरफ्लो

Question

पृष्ठभूमि:

को देखते हुए n गेंदों ऐसी है कि:

'a' balls are of colour GREEN 
'b' balls are of colour BLUE 
'c' balls are of colour RED 
... 

(पाठ्यक्रम a + b + c + ... = n का)

क्रमपरिवर्तन की संख्या है, जिसमें इन गेंदों व्यवस्थित किया जा सकता दिया जाता है द्वारा:

perm = n!/(a! b! c! ..) 

प्रश्न 1: मैं कैसे कर सकते हैं 'सुंदर ढंग से' perm तो गणना के रूप में के रूप में जब तक संभव के रूप में एक पूर्णांक अतिप्रवाह से बचने के लिए, और यह सुनिश्चित करें कि जब मैं की गणना किया हूँ, मैं या तो perm का सही मूल्य है, या मैं कि पता अंतिम परिणाम बह जाएगा?

असल में, मैं जीएनयू जीएमपी जैसे कुछ का उपयोग करने से बचना चाहता हूं।

वैकल्पिक रूप से, प्रश्न 2: क्या यह वास्तव में खराब विचार है, और क्या मुझे आगे बढ़ना चाहिए और जीएमपी का उपयोग करना चाहिए?

Answer 1

यदि आपके पास सीपीयू समय के ग्लोब हैं, तो आप सभी फैक्ट्रोरियल से सूचियां बना सकते हैं, फिर सूचियों में सभी संख्याओं का मुख्य कारकीकरण पा सकते हैं, फिर नीचे की तरफ के साथ शीर्ष पर सभी नंबरों को रद्द कर दें संख्या पूरी तरह से कम हो जाती है।

Answer 2

इन्हें बहुराष्ट्रीय गुणांक के रूप में जाना जाता है, जिन्हें मैं m(a,b,...) द्वारा इंगित करता हूं।

और आप कुशलतापूर्वक उन्हें इस पहचान (जो काफी साबित करने के लिए आसान होना चाहिए) का दुरुपयोग करके अतिप्रवाह से बचने की गणना कर सकते हैं:

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ... 
m(0,0,0,...) = 1 // base case 
m(anything negative) = 0 // base case 2 

तो यह प्रत्यावर्तन का उपयोग कर गुणांक गणना करने के लिए एक सरल बात है। ध्यान दें कि घातीय चलने वाले समय से बचने के लिए, आपको या तो अपने परिणामों को कैश करना होगा (पुनर्मूल्यांकन से बचने के लिए) या गतिशील प्रोग्रामिंग का उपयोग करना होगा।

ओवरफ़्लो की जांच करने के लिए, बस सुनिश्चित करें कि रकम अधिक नहीं हो पाएंगे।

और हां, यह सरल कार्य करने के लिए मनमानी सटीक पुस्तकालयों का उपयोग करना बहुत बुरा विचार है।

Answer 3

डेव सुझाए जाने का तरीका अतिप्रवाह-सुरक्षित तरीका है। आप प्रतिपादक जिसके साथ प्रधानमंत्री p योग

m = n; 
e = 0; 
do{ 
    m /= p; 
    e += m; 
}while(m > 0); 

से विभाजित करके n! सभी अभाज्य संख्या <= n के लिए a! आदि कि क्या की factorisations में p का घातांक घटाएँ मिल जाए, और आप बहुपद गुणांक के गुणनखंड है। वह गणना अतिप्रवाह हो जाती है अगर केवल अंतिम परिणाम बहती है। लेकिन बहुआयामी गुणांक तेजी से बढ़ते हैं, इसलिए आप पहले से ही काफी छोटे n के लिए अतिप्रवाह होगा। पर्याप्त गणना के लिए, आपको एक बिग्नम लाइब्रेरी की आवश्यकता होगी (यदि आपको सटीक परिणामों की आवश्यकता नहीं है, तो आप double एस का उपयोग करके थोड़ी देर तक प्राप्त कर सकते हैं)।

यहां तक ​​कि अगर आप एक bignum पुस्तकालय का उपयोग करें, यह बहुत बड़ा हो रहा से मध्यवर्ती परिणाम रखने के लिए सार्थक है, इसलिए बजाय factorials गणना और बड़ी संख्या में विभाजित करने की है, यह क्रम में भागों की गणना करने के लिए बेहतर है,

n!/(a! * b! * c! * ...) = n!/(a! * (n-a)!) * (n-a)!/(b! * (n-a-b)!) * ... 

और इन कारकों में से प्रत्येक गणना करने के लिए, के चित्रण के लिए दूसरा लेते हैं,

(n-a)!/(b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i 

prod = 1 
for i = 1 to b 
    prod = prod * (n-a+1-i) 
    prod = prod/i 

के साथ गणना की जाती है

अंततः भागों को गुणा करें। इसके लिए n डिवीजन और n + number_of_parts - 1 गुणा की आवश्यकता होती है, जो मध्यवर्ती परिणामों को मामूली रूप से छोटा रखते हैं।

Answer 4

this link के अनुसार, आप कई द्विपक्षीय गुणांक के उत्पाद के रूप में बहुराष्ट्रीय गुणांक की गणना कर सकते हैं, जिस तरह से पूर्णांक ओवरफ्लो को नियंत्रित करते हैं।

इससे मूल समस्या को एक द्विपक्षीय गुणांक के ओवरफ्लो-नियंत्रित गणना में कमी आती है।

Answer 5

नोटेशन: n! = prod(1,n) जहां प्रोड आप अनुमान लगा सकते हैं कि क्या करता है।

यह बहुत आसान है, लेकिन पहले आप किसी भी 2 धनात्मक पूर्णांक (i, n > 0) कि अभिव्यक्ति एक सकारात्मक पूर्णांक है के लिए है कि पता होना चाहिए:

prod(i,i+n-1)/prod(1,n) 

इस प्रकार विचार छोटे-छोटे टुकड़ों में विभाजित करने के लिए और n! की गणना काट करने के लिए है यथाशीघ्र।

a के साथ b और इसी तरह के साथ।

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!) 

इन कारकों में से

प्रत्येक एक पूर्णांक है, इसलिए यदि perm अतिप्रवाह नहीं होगा, न तो इसकी कारकों में से एक हो जाएगा।

हालांकि, एक ऐसे कारक की गणना में अंश या हर में एक अतिप्रवाह हो सकता है लेकिन है कि तब alternance में एक प्रभाग अंश में एक गुणा कर परिहार्य है:

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b 

कि जिस तरह से हर विभाग एक निकलेगा में पूर्णांक।