Hôm trước Mem nào hỏi kid bài này . Kid bảo search giúp mà kid cũng không thấy đâu chắc là kém rồi. Tuy nhiên hôm nay viết lên thế này vì câu hỏi của bạn còn mập mờ quá kid không biết trả lời sao cho thấu đáo vì năng lực có hạn .
Ví như số phần tử là một số cố định kid giả sử là 4 thì đơn giản bạn có thể làm như sau :
Cho 4 còn for chạy từ 0 -> 4 với các biến là i ,j,k,l nếu mà i,j,k,l này khác nhau thì đó là 1 hoán vị cần tìm và cậu sẽ in ra được đúng 24 hoán vị .
Tuy nhiên nếu người ta yêu cầu là đến 10 phần tử thì sao số hoán vị chắc chắn là rất lớn 10! và đặc biệt thuật toán trên mắc nhiều sai sót .
Điều đó vẫn chưa là ghê ghớm và bi giờ thì người ta nói rằng tui thích nhập bi nhiêu là quyền của tui thì chúng ta lại càng bối rối vì không thế biết mà dùng bao nhiều vòng for được. Kid cũng có suy nghĩ đến cái thuật toán như thế này . Không biết là giúp gì được U đọc và coi thử nhé . Nói trước là kid không viết code ra được chắc là nhờ anh em .
Giả sử ta có mảng 4 phần tử ( bi nhiêu cũng được không quan trọng )
Ta sẽ có một ma trận như sau :
Tớ giả sử các chỉ mục của mảng là từ a[1] -> a[4] để cậu dễ hiểu .
PHP Code:
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
Để tạo cái ma trận này thì đơn giản thôi đúng không >
Giờ tiếp tục nè ta thấy là số hoán vị của a[4] lúc này sẽ bằng tổng số hoán vị của từng hàng trong ma trận cộng lại đúng không ?
Cụ thể là !A[4] = !M[1][] + !M[2][] + !M[3][] + !M[4][] ;
Xét một hàng bất kì ví dụ là hàng thứ nhất M[1][] ;
Ta có số hoán vị trong đó sẽ như sau :
M[1][1] + !M[1][2 -> 4];
Mà số hoán vị từ M[2 -4] sẽ là tổng số hoán vị của 1 ma trận : Cụ thể như sau :
PHP Code:
2 3 4
3 4 2
4 2 3
Mà số hoán vị của ma trận này lại bằng số hoán vị của tất cả các dòng của nó .
Cậu có thấy là nó lặp lại không nào ! Hãy thử suy nghĩ và viết ra code nhé . Cuối cùng tớ sẽ dùng cách trên để liệt kê số hoán vị của 3 phần tử . Coi thử nhé .
int a[3] ;
PHP Code:
0 1 2
1 2 0
2 0 1
Hoán vị của 0 1 2 Gồm :
0 +
1 2
2 1
= 0 1 2 và 0 2 1
Tiếp tục hoán vị của 1 2 0 là ....
Tổng hợp lại ta sẽ có 6 hoán vị là : ....
Hi vọng là có cách khác hay hơn hoặc có anh em nào hiện thực thành code hoặc là bạn quyết định không viết bài này nữa he he
Số Tập Hợp Con Của 1 Tập Hợp !
Trả lời cùng với trích dẫn
)
Nguyên bản được gửi bởi hailoc12
