Thuật toán sắp xếp hiệu quả trong java

Question

Tôi đang cố gắng viết một phương thức sẽ tính tất cả các hoán vị của một bộ nguồn có thứ tự quan trọng. Tôi tin rằng đây được gọi là "sắp xếp". Những gì tôi có ý nghĩa bởi đây là:

{a} -> {{a}, {}} 
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}} 
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}} 

, vv ấn tượng của tôi là, cho một tập S, tôi nên tạo mỗi hoán vị của mỗi tập hợp con của Powerset S. Vì vậy, đầu tiên tạo ra Powerset, sau đó ánh xạ một hoán vị trên mỗi bộ.

Vấn đề là điều này vô cùng phức tạp - giống như O (∑n!/K!) Với k = 0..n.

Tôi tự hỏi nếu có bất kỳ thuật toán hiện có nào làm điều này loại điều rất hiệu quả (có lẽ là một thực hiện song song). Hoặc có lẽ ngay cả khi một thuật toán sức mạnh song song tồn tại và một thuật toán hoán vị song song tồn tại, tôi có thể kết hợp cả hai.

Suy nghĩ?

Answer 1

Thư viện ổi do google cung cấp chứa các phương pháp khác nhau để hoán đổi bộ sưu tập.

Xem javadoc của lớp com.google.common.collect.Collections2 here.

Answer 2

Để thực hiện điều này, trước tiên bạn tạo các kết hợp cho các vị trí 1-n trong đó n là số phần tử trong bộ nguồn. Ví dụ: nếu bạn có 3 phần tử, thì bạn sẽ có:

C (3, 3) = 1 kết hợp (abc)
C (3, 2) = 3 kết hợp (ab) (ac) (bc)
C (3, 1) = 3 kết hợp (a) (b) (c)

Bây giờ, bạn tạo hoán vị cho mỗi kết hợp.

Có các thuật toán nổi tiếng để tính hoán vị và kết hợp. Ví dụ: "Nghệ thuật lập trình máy tính" của Knuth, tập 4A, Mục 7.2.1.2 và 7.2.1.3, giải thích chính xác cách xây dựng các thuật toán có liên quan.