Tôi có một bộ N^2 số và N thùng. Mỗi thùng được cho là có số N từ tập hợp được gán cho nó. Vấn đề tôi đang phải đối mặt là tìm một bộ phân phối ánh xạ các con số tới các thùng, thỏa mãn ràng buộc, rằng mỗi cặp số có thể chia sẻ cùng một thùng chỉ một lần.Tìm một bộ hoán vị, với một ràng buộc
Phân phối có thể được biểu diễn độc đáo bằng ma trận NxN, trong đó mỗi hàng đại diện cho một thùng. Sau đó, vấn đề là tìm một tập hợp các hoán vị của các phần tử ma trận, trong đó mỗi cặp số chỉ chia sẻ cùng một hàng một lần. Nó không liên quan đến hàng nào, chỉ có hai số được gán cho cùng một số.
Ví dụ bộ 3 hoán vị đáp ứng các hạn chế đối với N = 8:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
0 8 16 24 32 40 48 56 1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63
0 9 18 27 36 45 54 63 1 10 19 28 37 46 55 56 2 11 20 29 38 47 48 57 3 12 21 30 39 40 49 58 4 13 22 31 32 41 50 59 5 14 23 24 33 42 51 60 6 15 16 25 34 43 52 61 7 8 17 26 35 44 53 62
Một hoán vị mà không thuộc vào bộ nói trên:
0 10 20 30 32 42 52 62 1 11 21 31 33 43 53 63 2 12 22 24 34 44 54 56 3 13 23 25 35 45 55 57 4 14 16 26 36 46 48 58 5 15 17 27 37 47 49 59 6 8 18 28 38 40 50 60 7 9 19 29 39 41 51 61
Vì của nhiều va chạm với hoán vị thứ hai, vì, ví dụ chúng đều ghép nối các số 0 và 32 trong một hàng.
Đếm ba là dễ dàng, nó bao gồm 1 hoán vị tùy ý, chuyển vị của nó và ma trận nơi các hàng được tạo từ các đường chéo của ma trận trước đó.
Tôi không thể tìm cách tạo ra một bộ bao gồm nhiều hơn. Nó có vẻ là một vấn đề rất phức tạp, hoặc một vấn đề đơn giản với một giải pháp không rõ ràng. Dù bằng cách nào tôi cũng sẽ biết ơn nếu ai đó có ý tưởng làm thế nào để giải quyết nó trong thời gian hợp lý cho trường hợp N = 8, hoặc xác định đúng tên học tập của vấn đề, vì vậy tôi có thể google cho nó.
Trong trường hợp bạn đang tự hỏi điều gì là hữu ích cho, tôi đang tìm một thuật toán lập lịch trình cho một công tắc ngang với 8 bộ đệm, phục vụ lưu lượng truy cập đến 64 điểm đến. Phần này của thuật toán lập lịch là đầu vào giao thông bất khả tri, và chuyển mạch theo chu kỳ giữa một số ánh xạ vùng đệm đích. Mục tiêu là để mỗi cặp địa chỉ đích cạnh tranh cho cùng một bộ đệm chỉ một lần trong chu kỳ đạp xe và để tối đa hóa độ dài của khoảng thời gian đó. Nói cách khác, để mỗi cặp địa chỉ đang cạnh tranh cho cùng một bộ đệm càng ít càng tốt.
EDIT:
Dưới đây là một số mã tôi có. CODE
Nó tham lam, nó thường chấm dứt sau khi tìm thấy hoán vị thứ ba. Nhưng nên tồn tại một tập hợp ít nhất N hoán vị thỏa mãn vấn đề.
Phương án thay thế sẽ yêu cầu chọn hoán vị tôi liên quan tìm kiếm hoán vị (I + 1..N), để kiểm tra nếu hoán vị tôi là một phần của giải pháp bao gồm số hoán vị tối đa. Điều đó đòi hỏi phải liệt kê tất cả các hoán vị để kiểm tra ở mỗi bước, điều này cực kỳ tốn kém.
Toàn bộ câu hỏi là một dài dòng chút. Nó không rõ ràng những gì bạn có ý nghĩa của cặp. Bạn có ý nghĩa gì bởi 'ràng buộc, rằng mỗi cặp số chỉ có thể chia sẻ cùng một thùng một lần.'? – Alex
Tôi đang gặp sự cố khi hiểu ràng buộc của bạn "mỗi cặp số chỉ có thể chia sẻ cùng một thùng một lần". Điều này có thực sự không đáng kể với bất kỳ sự sắp xếp nào của N^2 số duy nhất không? Bạn có thể cho thấy một sự sắp xếp mà không bị ràng buộc? –
Hạn chế cần phải được thỏa mãn cho toàn bộ các hoán vị. Vì vậy, nếu một hoán vị đặt các số 1 và 2 trên cùng một hàng, thì không có hoán vị nào khác trong tập hợp được phép đặt 1 và 2 trên cùng một hàng nữa. –