[PracticalWork_02] خوارزمية التجميعات الممكنة

[kachwahed]

السلام عليكم
أولا أعتذر عن التأخير
...
الحل بسيط جدا ويعتمد على فهم جيد لمبدأ عمل الخوارزمية
سأقوم بالشرح باستخدام جدول من الأحرف (Array of Chars) والمبدأ واحد (Integers/Strings...)
حسنا...
منهجية تفكير:

1. ما هو المطلوب؟
   

المطلوب من خلال أرقام مثلا: 2، 3، 4، 7 إيجاد جميع عمليات الجمع الممكنة بين هذه الأرقام دون تكرار الاحتمالات لأن 2+3=3+2

1. كيف نصل إلى هذا المطلوب؟
   

لتفادي الخلط بين الرتبة والعنصر سنستخدم حروف لاتينية: A, B, C, D
من الصعب جدا إيجاد الحل مباشرة دون تحليل النتائج
بعبارة أخرى دعونا نعيد ترتيب نتائج بشكل يسهل تفسيرها
بعد بضعة محاولات نحصل على عرض منطقي جدا:

كود :

A A+B A+B+C [color=Red] A+B+C+D [/color] A+B+[color=Blue]D[/color] A+C A+C+D A+D B B+C B+C+D B+D C C+D D

الآن بدأت الأمور تتضح شيئا فشيئا

1. كيف نحصل على الخوارزمية الصحيحة؟
   

من خلال هذا العرض الأخير نستنتج التحليل الآتي:
- البداية بإضافة أول عنصر (A)
-> إذا وجد عنصر بعده (B) نضيه إليه (لاحظ ترتيب التجميعات فوق!)
-> إذا لم يوجد شيء بعده (يعني وصلنا إلى آخر عنصر من الجدول هنا A+B+C+D حيث لا شيء بعد D)
-> -> نقوم بحذف العنصر الأخير (D) وتغيير الذي قبله بالعنصر الموالي (أنظر السطر الأحمر: حذفنا D وعوضنا الذي قبله (C) بالعنصر الموالي: D)
وهكذا انتهينا

1. كيف نحرر الخوارزمية؟
   

نقوم بترجمة كل سطر مما سبق إلى ما يوافقه من التعليمات مع تجزئة الكود.
- لدينا الجدول:

PHP كود :

var
  arChar: array[0..3] of char;
begin
  arChar[0] := 'A';
  arChar[1] := 'B';
  arChar[2] := 'C';
  arChar[3] := 'D'; 


لنحصل على ترتيب آخر عنصر من السلسلة:

PHP كود :

function GetLastCharIndex(var Item: string; arChar: array of Char): Integer;
begin
  if Item = '' then Result := -1 else
  Result := Pos(Item[Length(Item)], arChar)-1;
end; 


للحصول على عدد الاحتمالات الممكنة:

PHP كود :

function GetPossibilies(arChar: array of Char): Integer;
var
  i: Integer;
begin
  Result := 0;
  for i := 0 to High(arChar) do
    Result := Result+ nCr(High(arChar)+1, i);
end; 


nCr من هنا.
نبدأ بإضافة الأحرف إلى السطر في متغير نصي Item ثم إضافته إلى TListBox نسميها lbResults
كل ذلك يجري في إجرائية مستقلة تأخذ جدول من الأحرف كمعلمة (Parameter) ولتكن ParseNum

PHP كود :

procedure TfMain.ParseNum(var arChar: array of Char);
var
  ItemsCount: Integer;
{ نقوم بكتابة السطر على هذه السلسلة ثم نضيفها إلى القائمة }
  Item: string;
begin
{ حساب عدد الاحتمالات الممكنة}
  ItemsCount := GetPossibilies(arChar);
{ يستمر الطواف على الجدول مادمنا لم نبلغ عدد الاحتمالات الممكنة}
    while lbResults.Count < ItemsCount do begin
{  -> إذا لم نصل إلى نهاية الجدول }
      if High(arChar) > GetLastCharIndex(Item, arChar) then begin
{ هذا الفحص فقط لعدم إضافة علامة الجمع في أول السطر... }
        if Item = '' then
          Item := arChar[GetLastCharIndex(Item, arChar)+1]
        else
{  -> نضيف إلى السطر الحرف الموالي }
          Item := Item + '+'+ arChar[GetLastCharIndex(Item, arChar)+1];
      end else begin
{  -> أما إذا بلغنا نهاية الجدول: فنقوم بحذف آخر عنصر }
        Delete(Item, Length(Item)-1, 2);
{  ... ونغير العنصر الذي قبله بالعنصر الموالي من الجدول }
        Item[Length(Item)] := arChar[GetLastCharIndex(Item, arChar)+1];
      end;
{  -> في الأخير نطبع محتوى السطر }
      lbResults.Items.Add(Item);
    end;
end; 


وهكذا نصل إلى المطلوب. المثال مرفق ومعه مثال باستخدام TStringsـ ـ ـ

1. حوصلة
   

هذه خوارزمية بسيطة أسميتها Brute Force Shuffle مفيدة في بعض الحسابات التجارية وغيرها...
الهدف من التمرين ليس الخورازمية بذاتها وإنما طريقة فهم وتحليل المشكلات الحسابية لإيجاد الحلول البرمجية...
ملاحظة: يمكن طرح أمثلة أخرى لمن يريد. وحان الآن وقت طرح الملفات المصدرية.