الگوریتم محاسبه‌ی ضرایب دوجمله‌ای

تعریف ترکیب (Combination)

    تعداد حالت‌های انتخاب r (عدد صحیح و نامنفی) شیء از n (عدد صحیح و بزرگتر یا مساوی r) شیء را که ترتیب انتخاب اهمیت نداشته باشد، انتخاب r از n یا ترکیب r روی n گویند و به یکی از صورت‌های زیر نمایش می‌دهند:

    

    

    این عدد به ضریب دوجمله‌ای نیز مشهور است که یکی از محل‌های استفاده‌ی آن است.

    بر اساس اصل ضرب از اصول شمارش، ترکیب دو عدد از رابطه‌ی زیر قابل محاسبه است:

    

    

    که منظور از !n، فاکتوریل عدد صحیح و نامنفی n است:

    

    

    ترکیب دو عدد کاربردهای بسیاری در محاسبات ریاضی دارد:

    1- تعداد زیرمجموعه‌های r عضوی یک مجموعه‌ی n عضوی برابر ( C( n, r است.

    2- یکی از روش‌های محاسبه‌ی دنباله‌ی اعداد کاتالان استفاده از رابطه‌ی زیر است:

    

    

    3- ضرایب بسط دوجمله‌ای نیوتن با استفاده از ترکیب محاسبه می‌شود:

    

    

    4- تعداد جواب‌های معادله‌ی سیاله‌ی (یا دیوفانت) X₁ + X₂ + X₃ + ... + X_n = k با شروط X_i ≥ 0 و k ≥ 0 برابر با ( C( n + k - 1, k  است.

    5- ...

    هر کدام از این کاربردها و مباحث مرتبط، به بیان‌های مختلف در سوالات مسابقات برنامه‌نویسی نیز به چشم می‌خورد. مسأله‌ی مربی ناامید نمونه‌ای از این سوالات است.

    با توجه به شرط n ≥ r ≥ 0، اگر ترکیب r روی هر n را در سطرهای زیر هم بنویسیم، جدولی مثلثی شکل به وجود می‌آید که به مثلث خیام - پاسکال مشهور است:

    

    

پیاده‌سازی محاسبه‌ی ترکیب دو عدد

بر اساس تعریف فوق، ترکیب دو عدد با استفاده از تابع combination_1 در زبان برنامه‌نویسی ++C قابل محاسبه است:

    

long factorial( int n )

{

  if(  n == 0 )

  {

     return 1;

  }

  return n * factorial( n - 1 );

}

 

long combination_1( int n, int r )

{

  long fn = factorial( n );

  long fr = factorial( r );

  long fnr = factorial( n - r );

  return ( fn / ( fr * fnr ) );

}

 

    محاسبه‌ی ترکیب دو عدد نیاز به محاسبه‌ی فاکتوریل سه عدد n ،n - r و r دارد. محاسبه‌ی این سه فاکتوریل از مرتبه‌ی اجرای خطی هستند. در نتیجه تابع combination_1 هم از مرتبه‌ی خطی ( Ө( n است.

    میزان رشد تابع فاکتوریل با افزایش مقدار ورودی آن بسیار زیاد است. به عنوان مثال، !10 یک عدد هفت رقمی و !100 یک عدد 158 رقمی است. در نتیجه امکان ذخیره کردن دقیق اعداد حاصل از فاکتوریل در متغیرهای معمول زبان‌های برنامه‌نویسی ممکن نیست. این در حالی است که ترکیب دو عدد، علیرغم بزرگ بودن فاکتوریل ورودی‌های آن، ممکن است عدد کوچکی باشد:

    

    

    یک راه حل آن است که در صورت نیاز با استفاده از توابع و کلاس‌ها، ذخیره‌سازی اعداد صحیح بزرگ را تعریف و مدیریت کنیم. در این حالت می‌توان از بهینه‌سازی ضرب اعداد بسیار بزرگ و مسائل مربوطه هم استفاده کرد.

    راه حل دیگر استفاده از رابطه‌ی زیر است که از تعریف فوق به راحتی قابل اثبات است:

    

    

    این رابطه، یک الگوریتم بازگشتی برای محاسبه‌ی ترکیب روی n بر اساس ترکیب روی n - 1 را نشان می‌دهد.

    

پیاده‌سازی به روش تقسیم و غلبه

قطعه کد زیر رابطه‌ی فوق برای محاسبه‌ی ترکیب را به روش تقسیم و غلبه پیاده‌سازی می‌کند:

    

long combination_2( int n, int r )

{

  if( n == r || r == 0 )

  {

    return 1;

  }

  return ( combination_2( n - 1, r ) + combination_2( n - 1, r - 1 ) );

}

 

    این تابع فراخوانی بازگشتی را تا جایی ادامه می‌دهد که r برابر صفر یا n شود. در این حالت مقدار یک را باز می‌گرداند. پس می‌توان گفت خروجی نهایی از جمع زدن ( C( n, r تا عدد یک به دست می‌آید که به C( n, r ) - 1 عمل جمع نیاز دارد. بنابراین نیاز به ذخیره کردن اعداد بسیار بزرگ وجود ندارد. اما این روش معایبی نیز دارد.

    تعریف بازگشتی فوق به گونه‌ای است که محاسبات تکراری وجود دارد. فراخوانی تابع به صورت ( combination_2( n, r، دو فراخوانی ( combination_2( n - 1, r  و ( combination_2( n - 1, r - 1 را به دنبال دارد. خود این دو فراخوانی هر کدام به صورت مجزا تابع را به صورت ( combination_2( n - 2, r - 1 فراخوانی می‌کنند. یعنی ( combination_2( n - 2, r - 1 دو بار به صورت تکراری محاسبه می‌شود. هر چقدر عمق فراخوانی‌های بازگشتی بیشتر باشد، این تکرارها بیشتر می‌شود. چنین حالتی را در اصطلاح همپوشانی گویند.

    ثابت شده است که برای محاسبه‌ی ( C( n, r  با تابع combination_2، تعداد  C( n, r ) * 2 - 1 بار تابع  فراخوانی می‌شود. چنین عددی در بدترین حالت از مرتبه‌ی نمایی است که چندان قابل قبول نیست.

    نکته: بدترین حالت این محاسبه‌ زمانی است که r برابر بزرگترین عدد صحیح کوچکتر یا مساوی نصف n (یا به اصطلاح جزء صحیح n / 2) باشد. در این حالت به ازای یک n ثابت، ( C( n, r بیشترین مقدار خود را دارد (چرا؟).

    راه حلی که به نظر می‌رسد بتوان این همپوشانی را مهار کرد، ذخیره کردن محاسبات انجام شده در یک آرایه و استفاده‌ی مجدد از آنها در صورت نیاز است:

    

long comb[ MAX ][ MAX ] = { 0 };

 

long combination_3( int n, int r )

{

  if( r == n || r == 0 )

  {

    comb[ n ][ r ] = 1;

  }

  if( comb[ n ][ r ] == 0 )

  {

    comb[ n ][ r ] = combination_3( n - 1, r ) + combination_3( n - 1, r - 1 );

  }

  return comb[ n ][ r ];

}

 

    آرایه‌ی دو بعدی comb مقادیر ترکیب r روی n را در خود ذخیره می‌کند. در مقداردهی اولیه، تمامی عناصر آرایه را برابر صفر قرار می‌دهیم که مشخص می‌کند محاسبه‌ای انجام نشده است. در هر بار فراخوانی تابع، مقدار [ comb[ n ][ r بررسی می‌شود. اگر این مقدار برابر صفر باشد، نشان می‌دهد [ comb[ n ][ r قبلا محاسبه نشده است. چرا که ( C( n, r عدد مثبت و غیر صفر است. اما اگر مقدار آن غیرصفر باشد، این مقدار به عنوان نتیجه‌ی بازگشت داده می‌شود.

    توجه: مقداردهی اولیه‌ی صفر به تمامی عناصر آرایه - یا حداقل قسمت مورد نیاز - خود یک فرآیند زمان‌بر است.

    

پیاده‌سازی به روش برنامه‌نویسی پویا

تابع combination_3 اگرچه محاسبات تکراری را انجام نمی‌دهد، اما همچنان فراخوانی‌های بازگشتی تو در تو وجود داشته و سربار زمانی و حافظه ایجاد می‌کند. علت این مسأله در ذات روش تقسیم و غلبه و حل کل به جزء مسأله است. بر اساس روش برنامه‌نویسی پویا، مسأله را به صورت جزء به کل نیز می‌توان حل کرد.

    با توجه به جدول خیام - پاسکال، در روش کل به جزء و تقسیم و غلبه، با فراخوانی‌های بازگشتی از ( C( n, r به سمت مقادیر کوچکتر n حرکت کرده و با بازگشت مجدد از توابع، محاسبات انجام شده و مقدار ( C( n, r به دست می‌آید. در روش جزء به کل و برنامه‌نویسی پویا، محاسبات از بالای جدول خیام - پاسکال به سمت پایین و محل ( C( n , r انجام می‌شود. بنا به خاصیت مطرح شده برای ترکیب دو عدد، اعداد هر سطر از روی اعداد سطر بالاتر قابل محاسبه است. با پیش‌روی محاسبه‌ی این سطرها تا سطر nام - که ( C( n, r در آن قرار دارد - ، محاسبه به پایان می‌رسد:

    

long combination_4( int n, int r )

{

  int i, j;

  for( i = 0 ; i <= n ; i++ )

  {

    comb[ i ][ 0 ] = 1;

    comb[ i ][ i ] = 1;

  }

  for( i = 2 ; i <= n ; i++ )

  {

    for( j = 1 ; j <= i - 1 ; j++ )

    {

      comb[ i ][ j ] = comb[ i - 1 ][ j ] + comb[ i - 1 ][ j - 1 ];

    }

  }

  return comb[ n ][ r ];

}

 

    تابع combination_4 نه تنها مقدار ( C( n, r که تمام ترکیبات ( C( m, r با شرط n ≥ m را محاسبه و در آرایه‌ی comb ذخیره می‌کند. به عبارت دیگر، این تابع n + 1 سطر اول مثلث خیام - پاسکال را در آرایه‌ی comb ذخیره کرده و مقدار ( C( n, r را به عنوان خروجی تابع بازمی‌گرداند. پیچیده‌گی زمانی این الگوریتم ( Ө( n² است (چرا؟).

    اگر هدف صرفا پیدا کردن مقدار ( C( n, r باشد، می‌توان محاسبات را کمی محدودتر کرد. چرا که برای محاسبه‌ی ( C( n, r نیاز به محاسبه‌ی تمام مقادیر سطرهای فوقانی مثلث خیام - پاسکال نیست:

    

long combination_5( int n, int r )

{

  int i, j, min, max;

  for( i = 0 ; i <= n - r ; i++ )

  {

    comb[ i ][ 0 ] = 1;

  }

  for( i = 0 ; i <= r ; i++ )

  {

    comb[ i ][ i ] = 1;

  }

  for( i = 2 ; i <= n ; i++ )

  {

    min =  ( r + i - n > 1 ) ? ( r + i - n ) : 1;

    max = ( i - 1 < r ) ? i - 1 : r;

    for( j = min ; j <= max ; j++ )

    {

      comb[ i ][ j ] = comb[ i - 1 ][ j ] + comb[ i - 1 ][ j - 1 ];

    }

  }

  return comb[ n ][ r ];

}

 

    تعداد محاسبات حلقه‌ی داخلی این تابع برابر ( r ( n - r است که از شکل زیر نیز قابل استنباط است:

    

    

    در نتیجه مرتبه‌ی اجرای آن ( Ө( n r است که در بدترین حالت به ( O( n² منجر می‌شود.

    این الگوریتم را از نظر حافظه‌ی مصرفی نیز می‌توان بهینه کرد. همانگونه که بحث شد، هر سطر مثل خیام - پاسکال تنها به سطر قبلی خود وابسته است. بنابراین، اگر ذخیره کردن مقادیر غیر از ( C( n, r اهمیت نداشته باشد، می‌توان به جای آرایه‌ی دوبعدی و ذخیره کردن مقادیر سطرهای مختلف، از یک آرایه‌ی خطی برای ذخیره کردن سطر قبلی استفاده کرد. مقادیر سطر جدید را هم می‌توان با شروع از انتهای سطر - و نه ابتدا - در همان آرایه محاسبه و ذخیره کرد. چنین الگوریتمی حافظه‌ی مصرفی را از ( Ө( n² به ( Ө( n کاهش می‌دهد:

    

long combination_6( int n, int r )

{

  int i, j;

  long comb[ MAX ];

  for( i = 0 ; i <= n ; i++ )

  {

    for( j = i ; j >= 0 ; j-- )

    {

      if( j == 0 || j == i )

      {

        comb[ j ] = 1;

      }

      else

      {

        comb[ j ] = comb[ j ] + comb[ j - 1 ];

      }

    }

  }

  return comb[ r ];

}