[Bài toán] Biểu diễn n thành tổng các số tự nhiên không lớn hơn n.

Bài toán: Cho n là số nguyên dương. Biểu diễn n thành tổng các số tự nhiên không lớn hơn n.

Giải. Hai cách chia được gọi là đồng nhất nếu chúng có cùng các số hạng và chỉ khác nhau

về thứ tự sắp xếp. Bài toán được đặt ra là, cho số tự nhiên n, hãy duyệt mọi cách phân chia số n.

Chọn cách phân chia số n = b1 + b2 +...+bk với b1 > b2 >...> bk, và duyệt theo trình tự từ điển

ngược. Chẳng hạn với n = 7, chúng ta có thứ tự từ điển ngược của các cách phân chia như sau:

7

6        1

5        2

5        1        1

4        3

4        2        1

4        1        1        1

3        3        1

3        2        2

3        2        1        1

3        1        1        1        1

2        2        2        1

2        2        1        1        1

2        1        1        1        1        1

1        1        1        1        1        1        1

Như vậy, cách chia đầu tiên chính là n. Cách chia cuối cùng là dãy n số 1. Bây giờ chúng ta chỉ cần xây dựng thuật toán sinh kế tiếp cho mỗi cách phân chia chưa phải là cuối cùng.
Chương trình cài đặt như sau:
 

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
#define TRUE 1
#define FALSE 0
int n, C[MAX], k, count, Stop;
void Init(void){
 printf("\n Nhap n="); scanf("%d", &n);
 k = 1; count = 0; C[k] = n;
}
void Result(void){
 int i; count++;
 printf("\n Cach chia %d:", count);
 for (i = 1; i <= k; i++)
  printf("%3d", C[i]);
}
void Next_Division(void){
 int i, j, R, S, D;
 i = k;
 while (i>0 && C[i] == 1)
  i--;
 if (i>0){
  C[i] = C[i] - 1;
  D = k - i + 1;
  R = D / C[i];
  S = D % C[i];
  k = i;
  if (R>0){
   for (j = i + 1; j <= i + R; j++)
    C[j] = C[i];
   k = k + R;
  }
  if (S>0){
   k = k + 1; C[k] = S;
  }
 }
 else Stop = TRUE;
}
void Division(void){
 Stop = FALSE;
 while (!Stop){
  Result();
  Next_Division();
 }
}void main(void){
 Init();
 Division(); 
 _getch();

}

[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

Để xem giải thuật liệt kê hoán vị bạn có thể xem tại đây.

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.

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.

}