Chào mọi người.
Mọi người có thể giải thích cho mình tại sao chỗ này lại như vậy không
Cùng với k = 2, khi nào so sánh 0.2! < 2 <= 1.2!
khi nào so sánh 1.1! < 2 <= 2.2!
Link here
Hoán vị thứ k trong n!
Giống như hệ thập phân ấy mà 
5 Likes
bạn giải thích mình với 
Hi BK AnonymousNobita1.
Trước tiên bạn cần làm rõ bài toán (có lẽ vì mình hơi kém thống minh). Theo mình hoán vị không có thứ tự, không thể nói: Tôi nêm lần lượt muối, đường, tiêu thì có thứ tự sau đường, tiêu, muối. Tuy nhiên nếu hạn chế bài toán dựa trên tập các phần tử tự nhiên từ 1 đến n (hay chính xác hớn là thứ tự các phần tử trong 1 tập (các tập này luôn là rời rạc đếm được nên ánh xạ này luôn tồn tại)) thì có thể xây dựng một tập có thứ tự dựa trên thứ tự các phần tử trong đó. Bằng cách ánh xạ chuỗi các thứ tự (các thứ tự nhé 2, 4, 54 là một chuỗi và 2 có thứ tự 0, 4 có thứ tự 1, 54 có thứ tự 3 -> chuỗi thứ tự 0, 1, 2 về cơ bản luôn có song ánh như vậy.) Vậy bài toán trở thành tìm hoán vị thứ K của chuỗi thứ tự phần tử trong dãy.
5 Likes
Vấn đề là cách tìm như nào. Với một chuỗi như trên (dãy thứ tự phần tử trong chuỗi) thì bạn có thể tạo ra một hoán vị và định nghĩa cho nó một quan hệ thứ tự (nói một cách ngắn gọn là bạn nói phần tử này lớn hơn phần tử kia). Mình sẽ định nghĩa nó như này: Lấy giá trị của phần tử đó nhân với giai thừa của vị trí nó trong hoán vị đó rồi cộng hết lại.VD 1, 2, 3 có giá trị 1 x 3! + 2 x 2! + 3 x 1! (hoặc có thể đổi về 2!, 1!, 0!) khi đó mọi phần tử đều có thể so sánh với nhau dựa trên giá trị của nó (bạn có thể tự chứng minh nó thỏa mãn các tiên đề của quan hệ thứ tự)
5 Likes
Bây giờ tím thứ tự hoán vị như nào không lẽ tính hết ra rồi máp lại ? Tất nhiên là không. Dựa vào một tính chất của quan hệ thứ tự vừa định nghĩa ở trên. 1xxx << 2xxx < 3xxx < 4xxx (mình vị dụ với cuỗi 1, 2, 3, 4). Và trong mỗi đoạn 1xxx, 2xxx, 3xxx, 4xxx dều có 3! thừa số nữa. Vậy cách làm: só sanh k (20) và nhận thấy nó lớn hơn 3.3! và nhỏ hơn 4.3! nên số đó có dang 4xxx. Và xxx là một hoán vị trong chuỗi 1, 2, 3 (nếu bạn tìm nó dạng 3xxx thì xxx là một hoán vị trong chuỗi 1, 2, 4). Bài toán đệ quy lại là tim chuỗi thứ 2 trong dãy hoán vị của chuỗi (1, 2, 3). cũng giải tương tự thôi.
Vậy nếu k = 17 thì sao ?
2x3! < 17 <= 3x3! nến có dạng 3xxx với xxx là hoán vị của chuỗi 1, 2, 4. Và xxx là hoán vị thứ 17 - 12 = 5 của chuỗi 1, 2, 4. Nó sẽ có dang 1xx, 2xx, 4xx. Mỗi đoạn có 2! hoán vị. Vì 2x2! < 5 <= 3x2! (2, 3 là số lượng chứ không phải là 1xx, 2xx, 4xx). Vậy xxx sẽ có dạng 4xx. Và xx là hoán vị thứ 5 - 2x2! = 1 của chuỗi 1, 2. Nó sẽ có dạng 1x, 2x. Mỗi đoạn có 1! hoàn vị. cuối cùng tìm ra số tiếp theo là 1x và tất nhiên số cuối là 2 -> 3412.
6 Likes
Bạn giải thích hay quá, cám ơn bạn. Giờ mình mới hình dung được rõ hơn.
Bạn có thể cho mình hỏi thêm khi số n lớn thì cách giải quyết của bài trên với số lớn sẽ như thế nào? Mình chưa hình dung ra.
ví dụ với 4 số 1,2,3,4 :V
ta có các hoán vị của 1,2,3,4 là (sắp xếp theo thứ tự)
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ó thể chia ra làm 4 nhóm, mỗi nhóm chứa 3! phần tử.
- nhóm 0 tương ứng với vị trí thứ 0 … 5 (0 … 3! - 1)
- nhóm 1 tương ứng với vị trí thứ 6 … 11 (3! … 2*3! - 1)
- nhóm 2 tương ứng với vị trí thứ 12 … 17 (2*3! … 3*3! - 1)
- nhóm 3 tương ứng với vị trí thứ 18 … 23 (3*3! … 4*3! - 1)
muốn biến vị trí thứ m ở nhóm nào, chỉ cần lấy k chia 3! là ra :V Ví dụ m = 19 (tương ứng với hoán vị thứ k = 20, m là 0-index còn k là 1-index), thì nhóm của m là 19 / 3! = 3 là nhóm 3 (bắt đầu với 4 1 2 3)
tiếp tục tìm kiếm vị trí thứ v = m - 3*3!, là vị trí tương đối của phần tử thứ m trong nhóm 3 này. Ở ví dụ này vị trí tương đối trong nhóm 3 là 19 - 3*6 = 1
làm tương tự với thuật toán như trên: các hoán vị của 1,2,3 là
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
có thể chia thành 3 nhóm, mỗi nhóm 2! phần tử. Muốn biết vị trí thứ v ở nhóm nào chỉ cần lấy v / 2! là ra…
Chạy tay thuật toán: :V
- vị trí thứ 20, 1-index chuyển về 0-index là 19
- index nhóm = 19 / 3! = 3, vị trí tương đối tiếp theo = 19 - 3*3! = 1
- index nhóm = 1 / 2! = 0, vị trí tương đối tiếp theo = 1 - 0*2! = 1
- index nhóm = 1 / 1! = 1, vị trí tương đối tiếp theo = 1 - 1*1! = 0
- index nhóm = 0 / 0! = 0, vị trí tương đối tiếp theo = 0 - 0*0! = 0
- dừng vì ko có (-1)!
- các index nhóm là 3,0,1,0:
- [1,2,3,4] index 3 là số 4
- [1,2,3] index 0 là số 1
- [2,3] index 1 là số 3
- [2] index 0 là số 2
- vậy kết quả là 4 1 3 2
đpt O(n2) vì mỗi lần xóa 1 phần tử tốn trung bình n/2 lần shift các phần tử trong mảng đã sắp xếp, n lần xóa. Với 21! > 264 thì 212 chắc ko có vấn đề gì :V
5 Likes
Tìm một hoán vị (thứ k) nên có thể giới hạn n cỡ 20000
Một số tự nhiên k < n! có thể viết dưới dạng:
k = sigma(i=0..n-1) (d[i] * i!) với d[i] là số tự nhiên nhỏ hơn i
Thật vậy, 1*1! + 2*2! + ... + (n-1)*(n-1)! = n! - 1 
nên đây là một cách biểu diễn số.
Quẩy lên 
ta có thể định nghĩa thứ tự toàn phần bằng mảng đánh số từ 0:
O = [1, 2, 3, 4] với quy ước phần tử bé hơn đứng trước
Đầu tiên ta phải đưa k về dạng trên đã, ở trên đã đề cập một trong hai thuật toán
Tiếp theo xét một hoán vị π bất kì của O. Ta định nghĩa nghịch thế bên phải của một số trong π là số nằm bên phải nó nhưng bé hơn nó, hay i > j && π(i) < π(j).
Vậy cái này liên quan ntn? Ta có hoán vị (1234) là cực tiểu nên số hiệu là 0000 và (4321) là cực đại với số hiệu là… 3210 hay chữ số thứ i là số nghịch thế bên phải của π(i).
Giải thích như vậy là vì ta có thể khôi phục π mà không cần đụng đến O như sau: duyệt từ phải sang trái, cộng 1 cho tất cả những ô nào nằm bên phải mà không bé hơn ô đang xét.
Tại sao? Quay lại định nghĩa nghịch thế. Giả sử nếu π(i) đang xét chỉ lớn hơn 3 phần tử bên phải nó, mà π(j) lớn hơn những 5 phần tử thì cũng phải tăng 1 (xê ra ) để có chỗ cho π(i) “chen vào” chứ.
VD:
1 1 1 0 <- {0}
1 1 1 0 <- thêm 1 vào {0}
1 1 2 0 <-- π(2) lớn hơn 1 phần tử mà π(1) lớn nhỏ hơn 1pt vậy π(1) > π(2) rồi.
1 2 3 0
Nói cách khác, trước mỗi bước lặp thì bên phải là hoán vị đang hình thành
Bước cuối cùng là tra mảng O hay x => O[x].
p/s: tổng các nghịch thế bên phải là số nghịch thế của mảng.
6 Likes
n cỡ 20000 thì 20000! là cỡ 80 ngàn chữ số khi đó nổi chia tìm d[i] chắc cũng hết thời gian :V
tự chế ra 1 cái (Flat)WeightTree cũng xóa/truy cập phần tử theo index O(logn) được mà, rút ngắn thời gian xuống còn O(nlogn)
ví dụ 0 1 2 3 4 5 6 7 8
dựng WeightTree:
9
8 1
4 4 1
2 2 2 2 1
1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
pop phần tử thứ 5 (0-index):
9* 5 < 8: chọn left
8* 1 5 >= 4: chọn right, vị trí tương đối 5 - 4 = 1
4 4* 1 1 < 2: chọn left
2 2 2* 2 1 1 >= 1: chọn right
1 1 1 1 1 1*1 1 1 isLeaf --> kết quả là số 5
0 1 2 3 4 5 6 7 8
đã pop số 5, phải giảm weight trong đường dẫn đi 1 đơn vị
8*
7* 1
4 3* 1
2 2 1* 2 1
1 1 1 1 1 0*1 1 1
0 1 2 3 4 5 6 7 8
pop phần tử thứ 7
7*
7 0*
4 3 0*
2 2 1 2 0*
1 1 1 1 1 0 1 1 0* --> 8
0 1 2 3 4 5 6 7 8
pop phần tử thứ 4
6*
6* 0
4 2* 0
2 2 0* 2 0
1 1 1 1 0*0 1 1 0 --> 4
0 1 2 3 4 5 6 7 8
pop phần tử thứ 2
5*
5* 0
3* 2 0
2 1* 0 2 0
1 1 0*1 0 0 1 1 0 --> 2
0 1 2 3 4 5 6 7 8
pop phần tử thứ 3
4*
4* 0
3 1* 0
2 1 0 1* 0
1 1 0 1 0 0 0*1 0 --> 6
0 1 2 3 4 5 6 7 8
pop phần tử thứ 1
3*
3* 0
2* 1 0
1* 1 0 1 0
1 0*0 1 0 0 0 1 0 --> 1
0 1 2 3 4 5 6 7 8
pop phần tử thứ 2
2*
2* 0
2 0* 0
1 1 0 0* 0
1 0 0 1 0 0 0 0*0 --> 7
0 1 2 3 4 5 6 7 8
pop phần tử thứ 1
1*
1* 0
1* 0 0
1 0* 0 0 0
1 0 0 0*0 0 0 0 0 --> 3
0 1 2 3 4 5 6 7 8
pop phần tử thứ 0
0*
0* 0
0* 0 0
0* 0 0 0 0
0*0 0 0 0 0 0 0 0 --> 0
0 1 2 3 4 5 6 7 8
6 Likes
Khó hiểu quá mọi người ạ. Cám ơn mọi người.
Cái này để thêm mấy số 0 nữa thì thành full heap để nguyên không flat được vì ko biết nó có phải là child ko.
6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?