[Bài toán] Liệt kê tất cả các hoán vị của n phần tử.

Bài toán : Liệt kê các hoán vị của tập n phần tử. Cho X = { 1, 2,.., n }. Hãy liệt kê các hoán vị từ n phần tử của X.
Chương trình cài đặt bằng đệ quy quay lui.

//chương trình sẽ liệt kê tất cả các hoán vị của tập X={1,2,3,4} bằng phương pháp đệ quy quay lui.
//Kết quả của chương trình sẽ được ghi ra file HOANVI.OUT
#include<iostream>
using namespace std;
#define n 4 //Định nghĩa tập X gồm 4 phần tử X = {1,2,3,4}
int arr[n+1][2];//giá trị của arr[k][0] là mảng chứa các phần tử của mảng X  (1 <= k <= n+1)
    //giá trị của arr[k][1] là biến đánh dấu phần tử đó đã xuất hiện trong hoán vị hay chưa (1 <= k <= n+1)
int permute[n+1];// mảng 1 chiều ghi kết quả của các lần hoán vị.
void toPermute(int index){
 if(index > n){// nếu chỉ số trong bước lặp đệ quy lớn hơn n -> in ra kết quả hoán vị.
  for(int i=1;i<=n;i++){
   cout<<permute[i];
   if(i<n)cout<<",";
  }
  cout<<endl;
  return;
 }
 //Đệ quy để sinh ra hoán vị tiếp theo.
 for(int i=1;i<=n;i++){
  if(arr[i][1] == false){// kiểm tra phần tử i của tập X chưa xuất hiện trong hoán vị 
   permute[index] = arr[i][0];
   arr[i][1] = true;
   toPermute(index+1);
   arr[i][1] = false;
  }
 }
}
int main(){
 freopen("HOANVI.OUT","w",stdout);
 for(int i=1;i<=n;i++){
  arr[i][0] = i;
  arr[i][1] = false;
 }
 toPermute(1);
 return 0;
}

Output của chương trình

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,1,3
2,4,3,1
3,1,2,4
3,1,4,2
3,2,1,4
3,2,4,1
3,4,1,2
3,4,2,1
4,1,2,3
4,1,3,2
4,2,1,3
4,2,3,1
4,3,1,2
4,3,2,1

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.