Thuật toán cho các phép tính không lặp lại?

Question

Trong một chương trình tôi đang làm mà tạo ra đảo chữ cho một tập hợp các chữ cái, cách tiếp cận hiện tại của tôi là:

1. Nhận tất cả các kết hợp của tất cả các chữ
2. Lấy hoán vị của từng nhóm kết hợp
3. Sắp xếp các hoán vị kết quả theo thứ tự abc
4. Remove mục trùng lặp

câu hỏi của tôi gắn liền với toán học của hoán vị. Tôi tự hỏi nếu có thể tính toán kích thước mảng cần thiết để lưu trữ tất cả các mục còn lại sau khi loại bỏ các mục trùng lặp (sử dụng, nói, số lượng chữ cái lặp lại kết hợp với công thức hoán vị hoặc một cái gì đó).

Tôi xin lỗi về sự mơ hồ của câu hỏi của tôi, tôi vẫn đang nghiên cứu thêm về các kết hợp và hoán vị. Tôi sẽ cố gắng xây dựng mục tiêu của mình khi sự hiểu biết về sự kết hợp và hoán vị mở rộng, và một khi tôi làm quen với chương trình của mình (đó là dự án thời gian rảnh của mùa hè năm ngoái).

Answer 1

Nếu bạn có n yếu tố, và a[0] bản sao của một phần tử, a[1] bản sao của nguyên tố khác, và như vậy cho đến a[k], sau đó tổng số hoán vị khác nhau (lên đến bản sao) là n!/(a[0]! a[1]! ... a[k]!).

FYI, nếu bạn quan tâm, với Guava bạn có thể viết

Collection<List<Character>> uniquePermutations = 
    Collections2.orderedPermutations(Lists.charactersOf(string)); 

và kết quả sẽ là độc đáo hoán vị của các nhân vật, chiếm bản sao và tất cả mọi thứ. Bạn thậm chí có thể gọi phương thức .size() của nó - hoặc chỉ xem xét triển khai của nó cho các gợi ý. (Tiết lộ: Tôi đóng góp cho ổi.)

Answer 2

Tạo tất cả các hoán vị thực sự là ý tưởng tồi. Từ "tràn" ví dụ có 40320 hoán vị. Vì vậy, mức tiêu thụ bộ nhớ thực sự cao khi độ dài từ của bạn tăng lên.

Tôi tin rằng vấn đề bạn đang cố gắng giải quyết có thể được giảm xuống để tìm hiểu xem một từ có phải là đảo chữ cái của từ khác hay không.

Sau đó, bạn có thể giải quyết nó bằng cách đếm số lần mỗi chữ cái xuất hiện (nó sẽ là 26-tuple) và so sánh các tupples này với nhau.