Bài toán liệt kê các hoán vị của một tập có lặp theo thứ tự từ điển C/C++

Bài toán liệt kê các hoán vị của một tập có lặp theo thứ tự từ điển C/C++

Bài toán: Cho tập X gồm n chữ cái. X = {a,b,c,…} trong đó các chữ cái có thể lặp lại.

Xem qua lý thuyết

>> Giải thuật liệt kê hoán vị - liệt kê hoán vị tiếp theo theo thứ tự từ điển

Hãy liệt kê các hoán vị của tập X trên theo thứ tự từ điển.

[Input]

Có thể có nhiều hơn một test case trong file dữ liệu đầu vào PERMUTATION.INP. Dòng đầu tiên ghi số test case T.

Theo sau là danh sách test case.

Các dòng tiếp theo là string đầu vào.

[OutPut]

Ghi ra file PERMUTATION.OUT liệt kê tất cả các hoán vị theo thứ tự từ điển.

[I/O Example]

Input

2
bbjd
abcd

Output

bbdj ← in the order of b, b, d, and j
bbjd
bdbj
bdjb
bjbd
bjdb ← in the order of b, j, d, and b
dbbj
dbjb
djbb
jbbd
jbdb
jdbb

 

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Chương trình sinh hoán vị kế tiếp của tập n phần tử có lặp.

#include <cstdio>

#include <iostream>

#include<string.h>

using namespace std;

char str[11];

int n;

void toPermutation(){

          while(true){

                    //print out.

                    for(int index = 0;index <n; index++){

                              cout<<str[index];

                    }

                    cout<<"\n";

                    // find j that arr[j] < arr[j+1]

                    int j = n -2;

                    while(j>=0 && str[j] >= str[j+1]){

                              j--;

                    }

                    if(j == -1) break;

                    // find index on the right that is minimum and greater than arr[j].

                    int minRightIndex = j+1;

                    for(int k=j+2;k<n;k++){

                              if(str[k] <= str[minRightIndex] && str[k] > str[j]){

                                        minRightIndex = k;

                              }

                    }

                    // wrap j and minRightIndex

                    char temp = str[j];

                    str[j] = str[minRightIndex];

                    str[minRightIndex] = temp;

                    //revert arr from j+1 to n

                    for(int loop = 0; loop < (n -1 -j)/2;loop++){

                              char temp = str[j +1 + loop];

                              str[j+1+loop] = str[n- 1 -loop];

                              str[n -1 -loop] = temp;

                    }

                    

          }

}

int main(int argc, char** argv)

{

          int tc, T;

          freopen("PERMUTATION.INP", "r", stdin);

          freopen("PERMUTATION.OUT", "w", stdout);

          cin >> T;

          for(tc = 0; tc < T; tc++)

          {

                    cin>>str;

                    n = strlen(str);

                    for(int i=0;i<n-1;i++){

                              for(int j=i+1;j<n;j++){

                                        if(str[i] > str[j]){

                                                  char temp = str[i];

                                                  str[i] = str[j];

                                                  str[j] = temp;

                                        }

                              }

                    }

                    toPermutation();

        cout<<"\n";

                    // Print the answer to standard output(screen).

                    

          }

          return 0;//Your program should return 0 on normal termination.
 

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Apple phản hồi với lỗi bảo mật SMS trên iPhone

Apple phản hồi với lỗi bảo mật SMS trên iPhone

Một hacker jailbreak có biệt danh pod2g đã phát hiện ra một lỗi bảo mật nghiêm trọng liên quan tới hệ thống tin nhắn SMS trong hệ điều hành iOS 6 và ngay ngày hôm sau Apple đã phản hồi lại thông tin trên.

Workshop Photography - Cú bấm máy & Chuyện hậu kỳ trong nhiếp ảnh

Workshop Photography - Cú bấm máy & Chuyện hậu kỳ trong nhiếp ảnh

Buổi Workshop diễn ra vào lúc 9h sáng chủ nhật ngày 10/11/2019. Tại Văn phòng Keyframe : 06 Phan Đình Giót, P2, Q Tân Bình.

3 thuận lợi khi bạn sử dụng Git submodules with Drupal

3 thuận lợi khi bạn sử dụng Git submodules with Drupal

While building Drupal websites, we end up building modules for all sorts of random tasks – anything from simply reorganizing the contents of a node object or adding fields to the Site Information page to views plugins or huge integrations.