Tìm tất cả các hoán vị phù hợp với một bộ quy tắc

Question

Tôi được cung cấp số N và cho chúng áp dụng các quy tắc M về thứ tự của chúng. Các quy tắc được thể hiện trong một cặp các chỉ mục và mỗi cặp (A, B) nói rằng số có chỉ số A (số thứ A) phải sau SAU số thứ B - nó không phải là bên cạnh anh ta .

Ex: N = 4 
    1 2 3 4 
    M = 2 
    3 2 
    3 1 

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:) 

Thuật toán nên cung cấp cho tôi tất cả các hoán vị có sẵn mà không phá vỡ các quy tắc, như trong ví dụ - 3 phải luôn sau 2 và sau 1.

tôi đã cố gắng bruteforcing nhưng nó didn' t làm việc (mặc dù bruteforce nên làm việc ở đây, N là trong phạm vi (1,8).)

Bất kỳ ý tưởng?

Answer 1

Giống như gợi ý.

Bạn có thể xem bộ quy tắc của mình dưới dạng biểu đồ. Mỗi chỉ mục là một đỉnh, mỗi quy tắc là một cạnh chỉ đạo.

Bất kỳ trật tự chính xác của những con số (ví dụ: một hoán vị thỏa mãn các quy tắc) tương ứng với cái gọi là topological ordering của đồ thị trên. Để tạo ra tất cả thứ tự hợp lệ của các số của bạn, bạn cần tạo tất cả các thứ tự topo có thể có của biểu đồ đó.

P.S. Thuật toán đầu tiên cho thứ tự topo được đưa ra tại trang Wikipedia được liên kết đã cho phép một giải pháp khá đơn giản liệt kê tất cả các hoán vị hợp lệ. Nó sẽ mất một số nỗ lực và một số chăm sóc để thực hiện, nhưng nó không phải là khoa học tên lửa.

Answer 2

Buộc bắt buộc sẽ là going through every permutation, là O (N!) Và cho mỗi hoán vị chỉ lặp qua mọi quy tắc để xác nhận rằng chúng là aplpy, là O (M). Điều này kết thúc O (N! M) mà là loại vô lý, nhưng nó không nên "không làm việc" cho một tập nhỏ như vậy.

Answer 3

Thành thật mà nói, đặt cược tốt nhất của bạn là quay trở lại và nhận giải pháp lực lượng vũ phu hoạt động. Khi đã xong (và nếu bạn vẫn còn thời gian, vv) bạn có thể tìm kiếm một thuật toán tốt hơn.

CHỈNH SỬA cho người bỏ phiếu xuống. Học sinh (phải là) cố gắng hoàn thành bài tập về nhà vào thời gian. Bằng những âm thanh của nó, bài tập về nhà của anh ấy là một bài tập lập trình, nơi một giải pháp brute-force sẽ là đủ. Giúp anh ta tìm ra một thuật toán hiệu quả không giải quyết vấn đề REAL của anh ta. Trong trường hợp này, ông đã thử phương pháp tiếp cận bạo lực đơn giản (mà mọi người đồng ý phải làm việc cho các giá trị N nhỏ) và từ bỏ nó sớm để thử cái gì đó có lẽ khó khăn hơn. Bất kỳ nhà phát triển có kinh nghiệm nào cũng sẽ cho bạn biết rằng đây là một ý tưởng tồi. Học sinh cần và xứng đáng được nói như vậy, và nếu anh ấy là hợp lý, anh ấy sẽ chú ý. Nhưng rõ ràng, đó là sự lựa chọn của mình ...