Tìm các hoán vị độc đáo hiệu quả

Question

Tôi gặp vấn đề sau. Tôi cần tính toán hoán vị của một bộ; tuy nhiên, tập hợp có thể chứa hai phần tử giống nhau và do đó gây ra hoán vị lặp lại. Ví dụ:

Với bộ [ 0 0 1 2 ], các hoán vị bao gồm các khả năng:

1  2  0  0 
1  2  0  0 

Tuy nhiên, tôi muốn tránh hoán vị giống hệt như thế này. Trong MATLAB tôi chỉ có thể làm điều này:

unique(perms([ 0 0 1 2 ]), 'rows') 

Nhưng vấn đề ở đây là hiệu quả - Tôi đang làm điều này lặp đi lặp lại trong một vòng lặp for khổng lồ và phân loại theo yêu cầu của unique là quá chậm. Vì vậy, câu hỏi của tôi là: tôi có thể tính toán hoán vị duy nhất của thiên nhiên này trực tiếp mà không cần phải lặp lại kết quả sau đó không? Tôi đang làm việc trong MATLAB nhưng chỉ là một giải pháp chung có lẽ sẽ hữu ích, mặc dù một cái gì đó mà có thể được vectorized trong MATLAB có lẽ sẽ là lý tưởng!

Theo như tôi có thể thấy các câu hỏi hiện tại không đề cập chính xác vấn đề này, nhưng xin lỗi nếu điều này đã được trả lời trước đó.

Answer 1

Có vẻ như đây là sự cố thường xuyên xảy ra. Here là một tập tin của John d'Errico (uniqueperms) mà dường như giải quyết nó khá hiệu quả. Thay vào đó, có một FEX khác gửi here bởi Ged Ridgway; bạn sẽ phải lập hồ sơ một chút để xem cái nào nhanh hơn. Lưu ý rằng do những hạn chế của JIT của Matlab, các vòng lặp không được tăng tốc nếu chúng gọi các hàm không được xây dựng, do đó có thể sao chép-dán nội dung của các hàm này (và/hoặc sử dụng chúng một chút) bên trong vòng lặp của bạn.