نوشتن الگوریتم تر کیب اعداد

[maryam206]

برنامه ای بنویسید که ترکیب یک سری اعداد ورودی را ایجاد کند و نمایش دهد.

[Mashatan]

اینو نوشتم ببینید درست کار میکنه
راستش در محیط دلفی نوشتم نمی دونستم با چه ساختاری راحترین
یک Memo و EDIT احتیاج داره

function Fact(n : int64) : int64;

var

  i : integer;

begin

 result := 1;

 for i:=1 to n do

   result := result*i;

end;



function Swap(st : string; n : Int64) : string;

var

  nump : int64;

  take : integer;

begin

    nump := Fact(length(st)-1);

    result := '';

    repeat

         take := ((n-1) div nump) + 1;

         result := result + st[take];

         Delete(st,take,1);

         if (length(st) > 1) then

         begin

              n := ((n-1) mod nump)+1;

              nump := nump div (length(st));

         end;

    until (length(St) = 1);

    result := result + st;

end;



Procedure TForm1.Go;

var

  i,j:Integer;

begin

  Memo1.Lines.Clear;

  j:=Fact(Length(Edit1.Text ));

  for i:=1 to j do

    Memo1.Lines.Add( Swap(inttostr(i)+' -> '+Edit1.Text,i));

end;

[Kambiz]

جناب مشاطان لطف کردند و برنامه‌ای را به عنوان جواب ارائه کردند. اما چون پرسش در خصوص الگوریتم بود من از این فرصت استفاده میکنم و به تشریح این مسئله جهت یافتن الگوریتمی (متفاوت از آنچه آقای مشاطان ذکر کردند) به عنوان راه حل می‌پردازم.

----------------------------------------------------------------------------------------------------------

اگر قرار بود ترکیبهای (Permutations) موجود برای N عدد را بطور دستی بیابیم چه میکردیم؟ چند حالت را برای مقادیر مختلف N دنبال کنیم:

N = 0
خوب، در این حالت عددی وجود ندارد که بخواهیم ترکیبی بیابیم. :)

N = 1
فرض کنید که تنها عدد ما A باشد. بدیهی است که تنها می‌توانیم یک ترکیب بر روی کاغذ بیاوریم:

A

البته در این مورد باز صحبت خواهیم کرد!

N = 2
فرض کنید که اعداد ما عبارت باشند از A و B. در این حالت به دلخواه یک ترکیب را نوشته و سپس جای A و B را با هم عوض می‌کنیم:

A B
B A

N = 3
فرض کنید که اعدادمان A و B و C باشند. در این حالت ابتدا یکی از سه عدد را انتخاب کرده و روی کاغذ می‌نویسیم، به فرض A. سپس ترکیبات مختلف B و C را در مقابل آن می‌آوریم:

A B C
A C B

همین کار را با انتخاب B بعنوان عدد اول تکرار می‌کنیم:

B A C
B C A

و همچنین برای C:

C A B
C B A

خوب هر شش حالت ممکن را نوشتیم.

----------------------------------------------------------------------------------------------------------

اگر دقت کنید می‌بینید که روش یافتن ترکیبات حالت N = 2 را می‌توان با همان تعبیری که ترکیبات حالت N = 3 را یافتیم٬ بیان کنیم. بدین صورت که اول یکی از دو عدد را انتخاب کنیم و سپس تمام ترکیبات عدد دوم را که یکی بیش نیست (N = 1) در برابر آن بنویسیم و همین کار را با انتخاب عدد دوم تکرار کنیم.

حتی در مورد حالت N = 1 هم تعبیر بکار گرفته شده در مورد حالت N = 3 منطقی است. در این حالت تنها یک عدد برای انتخاب داریم و عدد دیگری در بین نیست (N = 0) که در برابر آن بنویسیم.

تنها در مورد حالت N = 0 است که نمی‌توان روش حالت N = 3 را به کار برد زیرا که چیزی برای یافتن وجود ندارد.

حال با این نتایج می‌توانیم روش یافتن ترکیبات n عدد را به صورت زیر بیان کنیم:

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

روش بالا روشی است بازگشتی (Recursive) بدین معنا که برای تعریف آن مجددا از خود آن بهره گرفته‌ایم. تنها در حالت N = 0 است که تعریف متفاوت می‌باشد که آن را مبنای بازگشت (Recursive Base) می‌نامند.

اکنون که تعریفی از روش یافتن تمام ترکیبات مجموعه‌ای از اعداد ارائه دادیم، می‌توانیم آن را بطور الگوریتمیک و به کمک دو زیر روال بیان کنیم. یک زیر روال برای یافتن ترکیبات N عدد و دیگری انتخاب عددی که با انتخاب آن ترکیبات مابقی اعداد را در برابر آن قرار می‌دهیم.

----------------------------------------------------------------------------------------------------------

ترکیبات اعضای مجموعه‌ی S با تعداد N عضو را پیدا کن:
...... اگر N برابر صفر بود
............ مجموعه‌ی S را چاپ کن
...... در غیر این صورت
............ حلقه به ازای هر عضو از 1 تا N
.................. عنصر بعدی از مجموعه‌ی S با تعداد N عضو را عضو اول قرار بده
.................. ترکیبات اعضای مجموعه‌ی S با تعداد N-1 عضو را پیدا کن
............ پایان حلقه
...... پایان اگر
پایان روال


عنصر بعدی از مجموعه‌ی S با تعداد N عضو را عضو اول قرار بده:
...... <span dir=ltr>S(1) -> T</span>
...... حلقه به ازای i از 1 تا N-1
............ <span dir=ltr>S(i+1) -> S(i)</span>
...... پایان حلقه
...... <span dir=ltr>T -> S(N)</span>
پایان روال

----------------------------------------------------------------------------------------------------------

توجه داشته باشید که در هنگام چاپ مجموعه‌ی S باید کلیه اعضای آن را چاپ شوند نه فقط N عضو مشخص شده توسط پارامتر روال. نکته دیگر اینکه در این الگوریتم خاص به منظور بهینه‌سازی الگوریتم می‌توان مبنای بازگشت را به جای صفر٬ یک قرار داد.

[S.Azish]

Option Explicit 



Private Sub Form_Load() 

' 

    Dim orgNumbers(6) As Integer 

    Dim nNumbers() As String 

    Dim i As Double 

    

    

    orgNumbers(0) = 1 

    orgNumbers(1) = 2 

    orgNumbers(2) = 3 

    orgNumbers(3) = 4 

    orgNumbers(4) = 5 

    orgNumbers(5) = 6 

    orgNumbers(6) = 7 

    'orgNumbers(7) = 8 

    'orgNumbers(8) = 9 

    'orgNumbers(9) = 0 

    

    nNumbers = CreateMultipleCases(orgNumbers) 

    

    List1.AddItem "Total numbers of cases: " & UBound(nNumbers) + 1   ' which is I! 

    

    For i = 0 To UBound(nNumbers) 

        List1.AddItem nNumbers(i) 

    Next 

    

' 

End Sub 



Private Function CreateMultipleCases(eNumbers() As Integer) As String() 

' 



    Dim i As Byte 

    Dim a As Byte 

    Dim j As Double 

    Dim iItemsCount As Integer 

    Dim eNewNumbers() As Integer 

    Dim eResult() As String 

    Dim fResult() As String 

    Dim iCounter As Double 

    

    iItemsCount = UBound(eNumbers) + 1 

    



    If iItemsCount > 1 Then  'For the last digit 

        ReDim eNewNumbers(iItemsCount - 2) As Integer 

            

        For a = 0 To iItemsCount - 1 

            Swap eNumbers(0), eNumbers(a) 

            For i = 1 To iItemsCount - 1 

                eNewNumbers(i - 1) = eNumbers(i) 

            Next 

            eResult = CreateMultipleCases(eNewNumbers) 

            For j = 0 To UBound(eResult) 

                ReDim Preserve fResult(iCounter) As String 

                fResult(iCounter) = eNumbers(0) & eResult(j) 

                iCounter = iCounter + 1 

            Next 

        Next 

    Else 

        ReDim fResult(0) As String 

        fResult(0) = eNumbers(0) 

    End If 

    

    CreateMultipleCases = fResult 

' 

End Function 



Private Sub Swap(ByRef Number_1 As Integer, ByRef Number_2 As Integer) 

' 

    Dim tmpInt As Integer 

    

    tmpInt = Number_1 

    Number_1 = Number_2 

    Number_2 = tmpInt 

' 

End Sub 

[S.Azish]

Option Explicit 



Private Sub Form_Load() 

' 

    Dim orgNumbers(6) As Integer 

    Dim nNumbers() As String 

    Dim i As Double 

    

    

    orgNumbers(0) = 1 

    orgNumbers(1) = 2 

    orgNumbers(2) = 3 

    orgNumbers(3) = 4 

    orgNumbers(4) = 5 

    orgNumbers(5) = 6 

    orgNumbers(6) = 7 

    'orgNumbers(7) = 8 

    'orgNumbers(8) = 9 

    'orgNumbers(9) = 0 

    

    nNumbers = CreateMultipleCases(orgNumbers) 

    

    List1.AddItem "Total numbers of cases: " & UBound(nNumbers) + 1   ' which is I! 

    

    For i = 0 To UBound(nNumbers) 

        List1.AddItem nNumbers(i) 

    Next 

    

' 

End Sub 



Private Function CreateMultipleCases(eNumbers() As Integer) As String() 

' 



    Dim i As Byte 

    Dim a As Byte 

    Dim j As Double 

    Dim iItemsCount As Integer 

    Dim eNewNumbers() As Integer 

    Dim eResult() As String 

    Dim fResult() As String 

    Dim iCounter As Double 

    

    iItemsCount = UBound(eNumbers) + 1 

    



    If iItemsCount > 1 Then  'For the last digit 

        ReDim eNewNumbers(iItemsCount - 2) As Integer 

            

        For a = 0 To iItemsCount - 1 

            Swap eNumbers(0), eNumbers(a) 

            For i = 1 To iItemsCount - 1 

                eNewNumbers(i - 1) = eNumbers(i) 

            Next 

            eResult = CreateMultipleCases(eNewNumbers) 

            For j = 0 To UBound(eResult) 

                ReDim Preserve fResult(iCounter) As String 

                fResult(iCounter) = eNumbers(0) & eResult(j) 

                iCounter = iCounter + 1 

            Next 

        Next 

    Else 

        ReDim fResult(0) As String 

        fResult(0) = eNumbers(0) 

    End If 

    

    CreateMultipleCases = fResult 

' 

End Function 



Private Sub Swap(ByRef Number_1 As Integer, ByRef Number_2 As Integer) 

' 

    Dim tmpInt As Integer 

    

    tmpInt = Number_1 

    Number_1 = Number_2 

    Number_2 = tmpInt 

' 

End Sub 

[Kambiz]

کد مربوط به الگوریتمی رو که قبلا" شرحش رو داده بودم به پاسکال اینجا می‌نویسم. دلیل اینکه اول ننوشتم برای این بود که فرصتی باشه تا خودتون الگوریتم رو کد کنید. و یک توضیح دیگه اینکه بجای آرایه‌ای از اعداد از آرایه‌ای از حروف استفاده شده تا علاوه بر ارقام بشه ترکیبات حروف رو هم بدست آورد.

ترکیبات اعضای مجموعه‌ی S با تعداد N عضو را پیدا کن:
...... اگر N کوچکتر یا برابر یک بود
............ مجموعه‌ی S را چاپ کن
...... در غیر این صورت
............ حلقه به ازای هر عضو از 1 تا N
.................. عنصر بعدی از مجموعه‌ی S با تعداد N عضو را عضو اول قرار بده
.................. ترکیبات اعضای مجموعه‌ی S با تعداد N-1 عضو را پیدا کن
............ پایان حلقه
...... پایان اگر
پایان روال

procedure Permutations(var S: String; N: Integer);

var

  I, J: Integer;

  Temp: Char;

begin

  if N <= 1 then

    Writeln(S)

  else

    for I := 1 to N do

    begin

      Temp := S[1];

      for J := 1 to N - 1 do

        S[J] := S[J + 1];

      S[N] := Temp;

      Permutations(S, N - 1);

    end;

end;

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

[shahmohammadi]

درك الگوريتم تركيب كمي سخته. براي همين برنامه تركيب رو يه تغيير كوچيكي دادم كه تو خروجي بشه فهميد كدوم چاپ مربوط به كدوم بازگشته. اميدوارم به دردتون بخوره.

#include <iostream.h>

#include <conio.h>



int l;

void perm(char *list,int i, int n)

{

  l++;

  for(int c=0;c<l;C++‎)

     cout<<" ";

  cout<<"{"<<i<<"-"<<n<<"\n";

  int j;

  char temp;

  if (i==n)

  {

     for(c=0;c<=l;C++‎)

    cout<<" ";

     cout<<list<<endl;

     //cout<<"   ";

  }

  else

  {

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

     {

    temp=list[i];

    list[i]=list[j];

    list[j]=temp;

    perm(list,i+1,n);

    temp=list[i];

    list[i]=list[j];

    list[j]=temp;

     }

  }

  for(c=0;c<l;C++‎)

     cout<<" ";

  cout<<"}\n";

  l--;

}

void main()

{

   clrscr();

   perm("123",0,2);

   getch();

}