Các phép có các giới hạn bổ sung

Question

Tôi có một tập hợp các mục, ví dụ: {1,1,1,2,2,3,3,3} và tập hợp các bộ giới hạn, ví dụ: {{3}, { 1,2}, {1,2,3}, {1,2,3}, {1,2,3}, {1,2,3}, {2,3}, {2,3}. Tôi đang tìm kiếm hoán vị các mặt hàng, nhưng các yếu tố đầu tiên phải là 3, và thứ hai phải có 1 hoặc 2, vv

Một hoán vị như vậy phù hợp là: {3,1,1,1,2, 2,3}

Có một thuật toán để đếm tất cả các hoán vị cho vấn đề này nói chung không? Có tên cho loại vấn đề này không?

Để minh hoạ, tôi biết cách giải quyết vấn đề này đối với một số loại "bộ hạn chế" nhất định. Đặt các mục: {1,1,2,2,3}, Hạn chế {{1,2}, {1,2,3}, {1,2,3}, {1,2}, {1, 2}}. Điều này bằng 2!/(2-1)!/1! * 4!/2!/2 !. Hiệu quả permuting 3 đầu tiên, vì nó là hạn chế nhất và sau đó permuting các mục còn lại, nơi có phòng.

Ngoài ra ... thời gian đa thức. Điều đó có thể không?

CẬP NHẬT: Điều này được thảo luận thêm tại các liên kết bên dưới. Vấn đề ở trên được gọi là "tính đối sánh hoàn hảo" và mỗi giới hạn hoán vị ở trên được biểu thị bằng {0,1} trên ma trận khe cho người cư ngụ.

• https://math.stackexchange.com/questions/519056/does-a-matrix-represent-a-bijection
• https://math.stackexchange.com/questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots

Answer 1

Tất cả các giải pháp khác ở đây là thời gian theo cấp số nhân - ngay cả đối với những trường hợp không cần thiết. Vấn đề này thể hiện cấu trúc con tương tự, và vì vậy nó cần được giải quyết bằng lập trình động.

Những gì bạn muốn làm là viết một lớp mà memoizes giải pháp cho bài toán:

class Counter { 
    struct Problem { 
    unordered_multiset<int> s; 
    vector<unordered_set<int>> v; 
    }; 

    int Count(Problem const& p) { 
    if (m.v.size() == 0) 
     return 1; 
    if (m.find(p) != m.end()) 
     return m[p]; 
    // otherwise, attack the problem choosing either choosing an index 'i' (notes below) 
    // or a number 'n'. This code only illustrates choosing an index 'i'. 
    Problem smaller_p = p; 
    smaller_p.v.erase(v.begin() + i); 
    int retval = 0; 
    for (auto it = p.s.begin(); it != p.s.end(); ++it) { 
     if (smaller_p.s.find(*it) == smaller_p.s.end()) 
     continue; 
     smaller_p.s.erase(*it); 
     retval += Count(smaller_p); 
     smaller_p.s.insert(*it);  
    } 
    m[p] = retval; 
    return retval; 
    } 

    unordered_map<Problem, int> m; 
}; 

Mã này minh họa lựa chọn một chỉ số i, mà nên được lựa chọn ở một nơi mà có v [i] .size() nhỏ. Một lựa chọn khác là chọn một số n, đây là một số mà trong đó có ít vị trí v mà nó có thể được đặt vào. Tôi muốn nói rằng tối thiểu hai yếu tố quyết định sẽ thắng.

Ngoài ra, bạn sẽ phải xác định hàm băm cho Sự cố - không nên quá khó khi sử dụng công cụ băm của quảng cáo.

Giải pháp này có thể được cải thiện bằng cách thay thế véc tơ bằng một tập hợp <> và xác định toán tử < cho unordered_set. Điều này sẽ thu gọn nhiều phần tử con giống hệt nhau thành một phần tử bản đồ duy nhất, và tiếp tục giảm thiểu mức tăng theo cấp số mũ.

Giải pháp này có thể được cải thiện hơn nữa bằng cách tạo các phiên bản Sự cố giống nhau ngoại trừ các số được sắp xếp lại băm thành cùng một giá trị và so sánh với cùng một giá trị.

Answer 2

Bạn có thể xem xét một giải pháp đệ quy có sử dụng một vũng chữ số (trong ví dụ bạn cung cấp, nó sẽ được khởi tạo {1,1, 1,2,2,3,3,3}), và quyết định, tại chỉ số được đưa ra như một tham số, có chữ số để đặt tại chỉ số này (sử dụng, tất nhiên, những hạn chế mà bạn cung cấp).

Nếu bạn thích, tôi có thể cung cấp mã giả.

Answer 3

Bạn có thể tạo cây. Cấp 0: Tạo nút gốc. Cấp 1: Nối từng mục từ "bộ giới hạn" đầu tiên làm con của gốc. Cấp 2: Gắn thêm từng mục từ bộ giới hạn thứ hai là con của mỗi nút Cấp 1. Cấp 3: Nối từng mục từ bộ giới hạn thứ ba là con của mỗi nút Cấp 2. ...

Số hoán vị sau đó là số lượng nút lá của cây cuối cùng.

Sửa

Đó là chưa rõ ràng những gì là có nghĩa là bởi "tập hợp các mặt hàng" {1,1,1,2,2,3,3,3}. Nếu điều đó có nghĩa là để hạn chế bao nhiêu lần mỗi giá trị có thể được sử dụng ("1" có thể được sử dụng 3 lần, "2" hai lần, vv) thì chúng ta cần thêm một bước:

• Trước khi gắn thêm một nút để cây, loại bỏ các giá trị được sử dụng trên đường dẫn hiện tại từ tập hợp các mục. Nếu giá trị bạn muốn chắp thêm vẫn có sẵn (ví dụ: bạn muốn nối thêm "1" và "1" chỉ được sử dụng hai lần cho đến nay) thì hãy thêm nó vào cây.

Answer 4

Để tiết kiệm dung lượng, bạn có thể tạo biểu đồ được hướng dẫn thay vì cây.

• Tạo nút gốc.
• Tạo một nút cho từng mục trong bộ đầu tiên và liên kết từ gốc tới các nút mới.
• Tạo một nút cho từng mục trong tập hợp thứ hai và liên kết từ mỗi mục đầu tiên được đặt thành từng mục được đặt thứ hai.
• ...

Số hoán vị là sau đó số lượng đường đi từ nút gốc đến nút của tập cuối cùng.