[C/C++] Tìm hoán vị củ N phần tử

[Duy Thanh]

Bạn nào biết làm ơn giúp mình doan code bài tìm hoán vi cua n phần tử:
ví dụ nhập n=3.sẽ in ra:
123
132
213
231
312
321
cảm ơn nhiều !

[kidkid]

uhm một bài toán hay đấy tạm thời thì kidkid chưa có cách giải , nếu mà tính số hoán vị thì dễ nhưng in số hoán vị thì có vấn đề đây ! Để nghĩ thử xem ?

[hikaru007]

Bài này nếu mình không nhầm thì Thuật toán ở đây là dùng phương pháp sinh(Thầy mình dạy vậy không biết tên có đúng không?).Ý nghĩa của phương pháp này là dùng để giải quyết bài toán liệt kê tất cả các tổ hợp thỏa mãn điều kiện nào đó.Sao cho không được bỏ sót hoặc lặp lại tổ hợp nào.
Bài toán có thể giải được nếu thỏa mãn 2 điều kiện:
-Có thể xác định được một thứ tự trên tập tất cả các cấu hình tổ hợp cần liệt kê.Từ đó có thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đã xác định.
-Xây dựng một thuật toán từ cấu hình chưa phải là cuối cùng đang có,đưa ra cấu hình kế tiếp.
Thuật toán nói đến ở trên gọi là thuật toán sinh.Cấu trúc chung của nó như sau:
Bước 1:Tạo cấu hình ban đầu.
Bước 2: Đưa ra cấu hình đang có.
Bước 3: Nếu cấu hình đang có là cấu hình cuối cùng thì kết thúc thuật toán:ngược lại thì sinh cấu hình kế tiếp và quay lại bước 2.
Vấn đề cơ bản đặt ra ở đây là Xây dựng thuật toán sinh cấu hình kế tiếp cấu hình đang có.
Có thể lấy ra một ví dụ điển hình là Bài toán liệt kê tất cả các hoán vị của N phần tử từ tập X={1,2,3,....,n}
Giải:Mỗi hoán vị từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự n thành phần a={a1,a2,a3,....,an} thỏa mãn a1,a2...an thuộc X và mỗi phần tử đôi một khác nhau.Tức là mỗi hoán vị là một sắp xếp lôn xộn các phần tử của Tập X.
Và trên tập các hoán vị của tập X có thể xác định một thứ tự đơn giản như sau:Hoán vị a={a1,a2,a3...,an} được coi là đứng trước hoán vị b={b1,b2,b3....bn}nếu tồn tại chỉ số k(1<=k<=n) sao cho a1=b1,a2=b2,a3=b3....ak-1=bk-1,ak<bk.Thứ tự như vậy được gọi là thứ tự "Từ Điển".Chẳng hạn bài của bạn nêu ra chính là một trường hợp của bài toán này.Với X={1,2,3} thì các hoán vị từ 3 phần tử của X được liệt kê theo thứ tự từ điển như sau:
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
Như vậy theo thứ tự từ điển thì hoán vị đầu tiên là (1,2,3...n) và hoán vị cuối cùng là (n,n-1....3,2,1).
Vậy giả sử a={a1,a2,a3...an} là môt hoán vị chưa phải là hoàn vị cuối cùng thì hoán vị kế tiếp của a được xác định như sau:
-Tìm từ phải qua trái trong hoán vị đang có chỉ số k đầu tiên thỏa mãn ak<ak+1.
-Trong các phần tử ở bên phải của ak và lớn hơn ak tìm phần tử nhỏ nhất a i.
-Đổi chỗ hai phần tử ak và ai.
-lật ngược đoạn các phần tử từ ak+1 đến an.
Mục đích của thuật toán đến đây bạn thấy chỉ là nhằm đưa lần lượt các số phía sau dãy hoán vị về phía trước và ngược lại,để đạt được cấu hình cuối cùng mong muốn.
Mình lại lấy thêm một ví dụ nữa để bạn hiểu.VD với n=6 và hoán vị đang xét là
a=(3,6,2,5,4,1) thì chỉ số k cần tìm là k=3 (vì a3=2<a4=5).Chỉ số i=5 (vì a5=4).Đổi chỗ a3 và a5 ta được hoán vị (3,6,4,5,2,1)và lật ngược đoạn từ ak+1 tức là đoạn từ a4 đến a6 (Đoạn 5,2,1) ta được hoán vị kế tiếp cần tìm là(3,6,4,1,2,5).
Như vậy mình đã trình bầy sơ qua về thuật toán sinh.Còn bạn muốn viết chương trình cụ thể để giải bài toán hoán vị có thể áp dụng thuật toán trên vào code của bạn.Vì bạn không nói rõ đề ra như thế nào nên mình không thể viết code cho bạn mà chỉ hướng dẫn bạn như vậy.Nếu bạn áp dụng tốt thì chắc là sẽ giải quyết được thôi.Hi vọng bạn hiểu và chúc bạn thành công.

[rox_rook]

Bài này khá cơ bản ! cho bạn code nè

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

using std::cout;
using std::cin;
using std::endl;
using std::setw;

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 << " Enter the number array's elements need to be permutated: ";  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 << "-------Permutation Algorithm--------------" << "\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--;
              
              
              if ( i >= 0 )
              {
                      k = n - 1 ;
                      while ( A[k] < A[i] )
                              k--;
                      
                      swap ( A[k], A[i] );
                      a = i + 1;
                      b = n - 1;
                                    while ( a < b )
                                    {
                                            swap ( A[a], A[b] );
                                            a++;
                                            b--;
                                    }
              }              
                      
      }
      while ( i >= 0 );
      getch();
}

[kidkid]

Hix thằng bạn mình nó nói thế này nè 4 vòng for ***g nhau , nếu mà có cặp i j k l nào đó trùng nhau thì không in ra , ngoài ra in hết là xong ?

[Leon88]

Mình cũng xin post 1 đoạn code của mình

#include<iostream.h>
#include<conio.h>
int n,i,j;
int a[100],b[100],c[100];
void hoanvi()
{
int k;
for (k=1;k<=n;k++)
if (b[k]==0)
{
j++;
c[j]=a[k];
b[k]=1;
if (j==n)
{
cout<<"\n";
for (i=1;i<=n;i++) { cout<<c[i]; }
}
hoanvi();
b[k]=0;
j--;
}
}
main()
{
clrscr();
cout<<"Nhap vao n : ";
cin>>n;
for (i=1;i<=n;i++) {a[i]=i;b[i]=0;} /*Muon nhap gi vao mang A[] cung dc*/
j=0;
hoanvi();
}

[haiquan]

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
int *B,*A,n;
void init(int*B,int n)
{
for (int i=1;i<=n;i++)
B[i]=true;
}
void process(int A[],int n,int count)
{
printf("\nhoan vi thu %5d:",count);
for(int i=1;i<=n;i++) printf("%d",A[i]);
}
void Try(int i,int n,int &count)
{
for(int j=1;j<=n;j++)
if(B[j])
{
A[i]=j;
B[j]=false;
if(i==n)
{
count++;
process(A,n,count);
}
else
Try(i+1,n,count);
B[j]=true;
}
}
void main()
{
clrscr();
printf("nhap so phan tu ");
scanf("%d",&n);
A=(int*)malloc(n*sizeof(int));
B=(int*)malloc(n*sizeof(int));
init(B,n);
int count =0;
Try(1,n,count);
free(A);free(B);
getch();
}

bài hoàn chỉnh

[SevenNo7]

Theo tôi thì bạn nên kiếm cuốn các bài giảng chuyên đề của thầy Lê Minh Hoàng ở trong 4rum đọc nó để có kiến thức rộng hơn thay vì chỉ kiếm code của nó để trả bài
Chúc vui.

[kenshin]

Mình cũng xin post 1 đoạn code của mình

Cảm ơn bạn, đoạn code của bạn hay lắm. Mình đang cần giải thuật đệ quy của bài này.

[tranvanluan2]

Mình nghĩ thuật toán này .Mọi người cho ý kiến
B1.Ta tính số hoán vị là n!
Ta dùng hàm đếm hoán vị là count
Ta đổi chỗ a[0] cho a[1]; in ra ;tăng count
Ta đổi chỗ a[1] cho a[2]; in ra;tăng count
...............

Ta đổi chỗ a[n-2] cho a[n-1]; in ra;tăng count
Cho đến khi count=n!-1 thì thôi