Thuật toán hoán vị n số nguyên

[boy_popping]

Nói thật là không biết thuật toán này có được gọi là khó hay không mà sao không thể giải nổi, kể cả copy bài giải của người khác vào xem mà cũng không hiểu

Mọi người xem và trả lời cho boy mấy câu hỏi có nêu trong bài luôn nghe, thanks mọi người nhiều

#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>

const int size = 100;
int A[size];

void swap ( int &r, int &c)
{
	int temp = r;
	r = c;
	c = temp;
}
void main()
{
      int n,i,k,a,b;
      cout << " Go vao day so cac phan tu can hoan vi: ";  cin  >> n;

      for ( i = 0; i < n; i++ ) A[i] = i+1;
      for ( i = 0; i < n; i++ ) cout << A[i] << setw(5);

      cout << "\n\n";
      cout << "#######################NTA#######################" << "\n\n";
      /* PERMUATION ALGORITHM */
      do
      {
	      for ( i = 0; i < n; i++ )
		      cout << A[i] << ","  << setw(3);

	      cout << "\n\n";// cin.get();

	      i = n - 2;
	      while ( i >= 0 && ( A[i] > A[i+1] ) ) /* Check whether it is a final configuration ( or not ) ?*/
		      i--;                   // ở đây có i-- với tác dụng gì
                      cout<<i<<endl;


	     // if ( i >= 0 )    //if o day khong can` dung ko
	      //{
		      k = n - 1 ;
		      while ( A[k] < A[i] )      //o day la so sanh a[n-2] va a[n-1] ?
			      k--;   //neu k-- thi se luon chay vong while vi A[i-1] < A[i] la dieu tat nhien

		      swap ( A[k], A[i] );             // o tren khai bao ham la swap(int &,int&) ma sao o duoi nay
 		      				       // co the dua vao ham` la cac mang?	
		      a = i + 1;                            //2 dong nay` co tac dung gi`
		      b = n - 1;
				    while ( a < b )                  //tai sao van tiep tuc chay vong while
				    {
					    swap ( A[a], A[b] );     //chay ham trong while de lam gi`
					    a++;                      // vi sao phai la a++ va b--
					    b--;
				    }
	    //  }

      }
      while ( i >= 0 );
      getch();
}

[AlexF]

Nói thật là không biết thuật toán này có được gọi là khó hay không mà sao không thể giải nổi, kể cả copy bài giải của người khác vào xem mà cũng không hiểu

Mọi người xem và trả lời cho boy mấy câu hỏi có nêu trong bài luôn nghe, thanks mọi người nhiều

nếu cậu năm nay lên năm thứ hai thì chắc đã học môn toán rời rạc rồi,hãy đọc lại lý thuyết toán rời rạc đi,vấn đề này trong diễn đàn thì rất nhiều mà trong sách vở cũng rất lắm

cậu có thể đọc lý thuyết của trường mình:

2.4.1. Sinh các hoán vị:
Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập {1,2,...,n}. Ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập {1,2,...,n} theo thứ tự từ điển. Khi đó, hoán vị a1a2...an được gọi là đi trước hoán vị b1b2...bn nếu tồn tại k (1  k  n), a1 = b1, a2 = b2,..., ak-1 = bk-1 và ak < bk.
Thuật toán sinh các hoán vị của tập {1,2,...,n} dựa trên thủ tục xây dựng hoán vị kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước a1 a2 ...an. Đầu tiên nếu an-1 < an thì rõ ràng đổi chỗ an-1 và an cho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho. Nếu tồn tại các số nguyên aj và aj+1 sao cho aj < aj+1 và aj+1 > aj+2 > ... > an, tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2, ..., an, rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj, aj+1, aj+2, ..., an vào các vị trí j+1, ..., n. Dễ thấy không có hoán vị nào đi sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra.

Thí dụ 11:

Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 4736521.
Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau là a3 = 3 và a4 = 6. Số nhỏ nhất trong các số bên phải của số 3 mà lại lớn hơn 3 là số 5. Đặt số 5 vào vị trí thứ 3. Sau đó đặt các số 3, 6, 1, 2 theo thứ tự tăng dần vào bốn vị trí còn lại. Hoán vị liền sau hoán vị đã cho là 4751236.
procedure Hoán vị liền sau (a1, a2, ..., an) (hoán vị của {1,2,...,n} khác (n, n1, ..., 2, 1))
j := n  1
while aj > aj+1
j := j  1 {j là chỉ số lớn nhất mà aj < aj+1}
k := n
while aj > ak
k := k - 1 {ak là số nguyên nhỏ nhất trong các số lớn hơn aj và bên phải aj}
đổi chỗ (aj, ak)
r := n
s := j + 1
while r > s
đổi chỗ (ar, as)
r := r - 1 ; s := s + 1
{Điều này sẽ xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần.}

[boy_popping]

@coder_gate: thank bạn nhiều
tuy bài trả lời của bạn rất chi tiết nhưng thực sự mình tệ mấy khoản này lắm
Thực ra học lập trình chỉ là để biết sơ sơ vừa đủ ra trường thôi
mình học mạng nên sẽ ưu tiên cho mạng hơn, ko tìm hiểu sâu về lập trình
Bạn nếu có thể hãy giúp mình giải đáp những thắc mắc đó nghe
mình cảm ơn nhiều lắm, mình học theo kiểu này chứ kiểu tư duy cao thì mình chịu ^^

[QuangHoang]

tuy bài trả lời của bạn rất chi tiết nhưng thực sự mình tệ mấy khoản này lắm
Thực ra học lập trình chỉ là để biết sơ sơ vừa đủ ra trường thôi
mình học mạng nên sẽ ưu tiên cho mạng hơn, ko tìm hiểu sâu về lập trình
Bạn nếu có thể hãy giúp mình giải đáp những thắc mắc đó nghe
mình cảm ơn nhiều lắm, mình học theo kiểu này chứ kiểu tư duy cao thì mình chịu ^^

Bạn học chủ yếu về mạng, rất tốt. Nhưng lập trình sẽ giúp bạn tăng khả năng tư duy, hiểu rõ về hệ cách hoạt động của máy tính và phần mềm. Một số giải thuật của lập trình cũng rất hữu dụng trong lĩnh vực mạng.
Mình viết vậy để bạn thấy hữu ích và yêu lập trình hơn. Chúc bạn học tốt!