Tìm cấu hình thứ k trong hoán vị của n phần tử

Bài toán này rất thú vị: Tìm cấu hình thứ k trong hoán vị của n phần tử từ 1 tới n.

Bài toán tương tự: Giải đề thi Olympic Tin học Sinh viên 2004 – Biểu diễn số nguyên lớn bằng mảng

Ví dụ: Cho n = 4, vậy cấu hình thứ 20 trong hoán vị của 4 phần tử từ 1 tới 4 là:

4 1 3 2

Gợi ý: Tư tưởng, có một chút, một chút xíu thôi (không hoàn toàn) giống với tư tưởng của Bài toán Josephus – Tự sát.

Mình liệt kê ra 24 hoán vị của 4!, các bạn nhìn vào đây sẽ rút ra thuật toán cho mình:

  1:  1  2  3  4
  2:  1  2  4  3
  3:  1  3  2  4
  4:  1  3  4  2
  5:  1  4  2  3
  6:  1  4  3  2
  7:  2  1  3  4
  8:  2  1  4  3
  9:  2  3  1  4
 10:  2  3  4  1
 11:  2  4  1  3
 12:  2  4  3  1
 13:  3  1  2  4
 14:  3  1  4  2
 15:  3  2  1  4
 16:  3  2  4  1
 17:  3  4  1  2
 18:  3  4  2  1
 19:  4  1  2  3
 20:  4  1  3  2
 21:  4  2  1  3
 22:  4  2  3  1
 23:  4  3  1  2
 24:  4  3  2  1

Lời giải:

Hướng dẫn cho bài toán ở trên:

Ví dụ, trường hợp n = 4 và k = 20. Ta thấy:

3.3! < 20 <= 4.3! => Chọn số 4 (số mang thứ tự thứ 4 trong dãy {1, 2, 3, 4}). Các số còn lại là {1, 2, 3} được đánh số lại là 1, 2, 3. Ta có: 20 – 3.3! = 2

0.2! < 2 <= 1.2! => Chọn tiếp số 1 (số mang thứ tự thứ 1 trong dãy {1, 2, 3}). Các số còn lại đánh số là: {2, 3}. Đánh số lại các số này là: 1, 2. Ta có: 2 – 0.2! = 2

1.1! < 2 <= 2.2! => Chọn tiếp số 3 (số mang thứ tự thứ 2 trong dãy {2, 3}). Các số còn lại chỉ còn 2. Đánh số lại các số này: 2. Ta có: 2 – 1.1! = 1

0.0! < 1 <= 1.0! => Chọn tiếp số 2 (số mang thứ tự thứ 1 trong dãy {2}). Các số còn lại là {} – tập rỗng. Ta có 1 – 0.0! = 0. => Dừng

Vậy hoán vị thứ 20 của {1, 2, 3, 4} là: 4 1 3 2

Ví dụ 2:

Trường hợp n = 3, k = 5.

Các hoán vị của {1, 2, 3} là:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

2.2! < 5 <= 3.2! => Chọn số 3 (số mang thứ tự thứ 3 trong dãy {1, 2, 3}). Các số còn lại là {1, 2} được đánh số lại là 1, 2. Ta có: 5 – 2.2! = 1

0.1! < 1 <= 1.1! => Chọn tiếp số 1 (số mang thứ tự thứ 1 trong dãy {1, 2}). Các số còn lại đánh số là: {2}. Đánh số lại các số này là: 1. Ta có: 1 – 0.1! = 1

0.0! < 1 <= 1.0! => Chọn tiếp số 2 (số mang thứ tự thứ 1 trong dãy {2}). Các số còn lại là {} – tập rỗng. Ta có 1 – 0.0! = 0. => Dừng

Vậy hoán vị thứ 5 của {1, 2, 3} là: 3 1 2

Từ đây, bạn có thể suy ra thuật toán với độ phức tạp O(n).

Chú ý: Một cách làm trong trường hợp bạn không nghĩ ra thuật giải là dùng thuật giải với độ phức tạp O(n!) với thuật toán Quay lui.

Thuật toán quay lui sử dụng trong trường hợp xấu nhất k = n!, tương ứng với việc duyệt tất cả các cấu hình hoán vị của n phần tử.

O(n) << O(n!) (Kí hiệu: << nghĩa là: nhỏ hơn rất rất nhiều)

Với bài toán này, chúng ta chỉ hạn chế n = 20. Nguyên nhân: 20! = 2.432.902.008.176.640.000 (2,43290200817664 * 10^18) (Đây nằm trong giới hạn của kiểu unsigned long long: 2^64 – 1)Khi k = 20!, n = 20 thì thuật toán với Quay lui chạy mất thời gian là: 20! / (10^8 * 366 * 24 * 60 * 60) = 769,3603 năm.

Đây là ví dụ rất điển hình khi mô tả trường hợp BÙNG NỔ TỔ HỢP.

Còn thuật toán O(n) với n = 20 thì chỉ chạy với thời gian khoảng 0.03 giây là xong

Với n > 20, chúng ta cần cài đặt số lớn với các phép tính: phép nhân, phép so sánh, phép trừ. Nên sử dụng hệ cơ số 10^9 (1 tỷ) trong trường hợp này (thời gian chạy cũng rất nhỏ).

Code: .cpp

#include
#include

#define fi "HOANVI.INP"

using namespace std;

typedef unsigned long long ull;
ull dem = 0;

int n;
ull k;
ull * gt;
int * ThuTu;

void Nhap() {
    fstream f(fi, ios :: in);
    f >> n;
    f >> k;
    f.close();
}

void Init() {
    ThuTu = new int[n+1];
    int i;
    for (i=1; i<=n; i++) ThuTu[i] = i;
}

void XoaViTri(int k) {
    int i;
    for (i=k; i<n; i++) ThuTu[i] = ThuTu[i+1];
    n--;
}

void TinhGiaiThua(int n) {
    gt = new ull[n+1];
    gt[0] = 1;
    int i;
    for (i=1; i<=n; i++) gt[i] = i*gt[i-1]; }   void ThucHien() {     int x;     while (n > 0) {
        //x = TimKiemNhiPhan(k, 1, n, n);
        x = gt[n]/gt[n-1];
        if (gt[n]%gt[n-1] != 0) x++;
        cout << ThuTu[x] << "   ";
        k = k - (x-1)*gt[n-1];
        XoaViTri(x);
    }

}

int main() {
    Nhap();
    Init();
    TinhGiaiThua(n);
    ThucHien();
    //cout << endl << "k = " << k;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: