كيف تكتب هذه الخوارزمية لمجموعات كبيرة في الطريقة الأكثر إحكاما؟

Question

عدد مجموعات k العناصر التي يمكن استرجاعها من N يتم وصف العناصر من قبل الصيغة التالية.

             N! 
c =  ___________________ 
       (k! * (N - k)!)

مثال سيكون كم مجموعات من 6 Balls يمكن رسمها من طبل 48 Balls في التعادل اليانصيب.

تحسين هذه الصيغة لتشغيلها مع أصغر o تعقيد الوقت

كان هذا السؤال مستوحى من محرك Wolframalpha Math الجديد وحقيقة أنه يمكن أن يحسب مجموعات كبيرة للغاية بسرعة كبيرة. على سبيل المثال ومناقشة لاحقة حول الموضوع في منتدى آخر.

http://www97.wolframalpha.com/input/؟i=20000000+ Choose+15000000.

سوف نشر بعض المعلومات / الروابط من تلك المناقشة بعد بعض الناس تأخذ طعنة في الحل.

أي لغة مقبولة.

Answer 1

لاحظ أن Wolframalpha ترجع "تقريب عشري". إذا كنت لا تحتاج إلى دقة مطلقة، فيمكنك أن تفعل الشيء نفسه عن طريق حساب الحقائق تقريب ستيرلينغ.

الآن، يتطلب تقريب ستيرلينغ تقييم (N / E) ^ n، حيث E هو قاعدة اللوغاريتم الطبيعية، والتي ستكون إلى حد بعيد أبطأ عملية. ولكن يمكن القيام بذلك باستخدام التقنيات المبينة في آخر stackoverflow post..

إذا كنت تستخدم الدقة المزدوجة وتكرار التربيع لإنجازه للأسف، فستكون العمليات:

• 3 تقييمات تقريبية Stirling، كل منها يتطلب الضرب O (سجل ن) وتقييم جذر مربع واحد.
• 2 الضراع
• 1 الانقسامات

ربما يمكن تخفيض عدد العمليات مع القليل من الذكاء، ولكن التعقيد الزمني الإجمالي سوف يكون س (سجل N) مع هذا النهج. يمكن التحكم فيها جدا.

تحرير: يجب أن يكون هناك أيضا الكثير من الأدبيات الأكاديمية حول هذا الموضوع، بالنظر إلى مدى شائع هذا الحساب. مكتبة جامعية جيدة يمكن أن تساعدك في تتبعها.

Edit2: أيضا، كما هو مذكور في استجابة أخرى، ستضغط القيم بسهولة مزدوجة، لذلك يجب استخدام نوع نقطة عائمة مع دقة ممتدة للغاية لتوفير القيم الكبيرة المعتدلة من K و N.

Answer 2

بيثون: في(دقيقة [ك,ن-ك]²)

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

التحليلات:

• حجم. p و q سوف تزيد الخطي داخل الحلقة، إذا n-i و 1+i يمكن اعتبارها أن يكون لها حجم ثابت.
• ستزيد تكلفة كل الضرب أيضا خطيا.
• هذا المبلغ من جميع التكرار يصبح سلسلة حسابية k.

استنتاجي: في(k²)

إذا تم إعادة كتابتها لاستخدام أرقام النقطة العائمة، فستكون الضربات عمليات ذرية، لكننا سنفقد الكثير من الدقة. انها حتى يفيض ل choose(20000000, 15000000). وبعد (ليست مفاجأة كبيرة، لأن النتيجة ستكون حوالي 0.2119620413 × 10^4884378.)

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

Answer 3

سأحلها في الرياضيات:

Binomial[n, k]

رجل كان من السهل ...

Answer 4

بيثون: تقريب في في(1) ?

باستخدام Python التنفيذ العشري لحساب التقريب. نظرا لأنه لا يستخدم أي حلقة خارجية، فإن الأرقام محدودة الحجم، وأعتقد أنه سينفذ في في(1).

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

مثال:

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

أي أعلى، وسوف يتفوق. يبدو أن الأسهم يقتصر على 40000000.

Answer 5

بالنظر إلى عدد معقول من القيم ل n و k، احسبها مقدما واستخدام جدول البحث.

إنها تهرب من المشكلة في بعض الأزياء (يمكنك تفريغ الحساب)، لكنها تقنية مفيدة إذا كنت تواجه تحديد أعداد كبيرة من القيم.

Answer 6

ماتلاب:

• طريقة الغشاش (باستخدام الوظيفة المدمجة nchoosek.): 13 حرفا، س (؟)

  nchoosek(N,k)
  

• بلدي الحل: 36 حرفا، O (دقيقة (K، NK))

  a=min(k,N-k);
  prod(N-a+1:N)/prod(1:a)
  

Answer 7

أعلم أن هذا سؤال قديم حقا لكنني كافح مع حل لهذه المشكلة لفترة طويلة حتى وجدت واحدة بسيطة حقا مكتوبة في VB 6 وبعد أن تقوم بتنفيذها إلى C #، وهنا النتيجة:

public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}

الرمز النهائي بسيط جدا لن تصدق أنه سيعمل حتى تقوم بتشغيله.

أيضا، المقالة الأصلية يعطي بعض التفسير اللطيف حول كيفية توصله إلى الخوارزمية النهائية.