Làm thế nào tôi có thể đảm bảo rằng khi tôi xáo trộn câu đố của mình, tôi vẫn kết thúc với một hoán vị thậm chí?

Question

Tôi quan tâm làm một thực hiện các 14-15 puzzle:

tôi là tạo ra một mảng với các giá trị 0 - 15 trong thứ tự tăng dần:

S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Bây giờ, những gì tôi muốn làm là trộn chúng để tạo ra một thể hiện mới của câu đố. Tuy nhiên, tôi biết rằng nếu tôi tạo ra một bảng với một "hoán vị lẻ" hơn là không thể giải quyết được.

Wikipedia nói rằng tôi cần phải tạo câu đố với một hoán vị thậm chí. Tôi tin rằng điều này có nghĩa rằng tôi chỉ đơn giản là phải làm đảm bảo tôi làm một số lượng thậm chí của các giao dịch hoán đổi?

Làm cách nào để sửa đổi Fisher-Yates để tôi đảm bảo rằng tôi kết thúc với một hoán vị thậm chí ở cuối? Nếu tôi thực hiện hoán đổi cho mỗi phần tử trong mảng có 16 hoán đổi mà tôi tin là một hoán vị thậm chí. Tuy nhiên, tôi có cần phải lo lắng về việc trao đổi với chính nó? Có cách nào khác để đảm bảo tôi có một câu đố hợp lệ không?

Answer 1

Tôi sẽ không thực sự cố gắng sửa đổi thuật toán, có lẽ nó vẫn đang tranh luận cho ứng dụng này. Từ những gì tôi thấy có hai tùy chọn:

1. Chỉ cần trộn lại cho đến khi bạn có được hoán vị thậm chí. Điều này có lẽ sẽ bỏ đi một nửa hoán vị trung bình (tốt, có thể nhiều hơn một chút), nhưng công việc phụ có thể rất không đáng kể.
2. Trộn bảng bằng cách sử dụng di chuyển của trò chơi. Đó là, chỉ cần làm vài trăm động tác ngẫu nhiên. Vì bạn không lấy tất cả các phần và lắp ráp lại chúng, bạn không thể tạo ra một trạng thái không thể giải quyết được.

Answer 2

Fisher-Yates tùy thuộc vào khả năng trao đổi bất kỳ phần tử nào với bất kỳ phần tử nào khác. Vì điều này vi phạm vật lý của câu đố, tôi không nghĩ bạn có thể sử dụng nó ở đây.

Giải pháp ngây thơ là làm những gì bạn sẽ làm theo cách thủ công, chọn ngẫu nhiên một trong các ô liền kề với ô trống và trao đổi với nó. Tôi không biết bạn cần phải thực hiện bao nhiêu lần hoán đổi để có được sự xáo trộn tốt.

Answer 3

Bạn sẽ có thể sử dụng Fischer-Yates.

• Tạo hoán vị ngẫu nhiên bằng Fischer-Yates.
• Kiểm tra xem nó có còn không.
• Nếu không đổi, hãy hoán đổi hai phần tử đầu tiên của hoán vị.

Xem xét hoán vị thậm chí P = x1 x2 .... xn.

Fischer yates tạo P với xác suất 1/n !.

Nó tạo x2 x1 ... xn với xác suất 1/n !.

Do đó xác suất mà quy trình trên tạo ra hoán vị P là 2/n! = 1/(n!/2)

n!/2 là số hoán vị thậm chí.

Do đó, quy trình trên tạo ra các hoán vị thậm chí với cùng xác suất.

Để kiểm tra xem hoán vị có đồng đều hay không: hãy tính số chẵn lẻ của số inversions trong hoán vị.

Answer 4

Dưới đây là những gì tôi tìm thấy đã trả lời ở đây:.

"Vấn đề này cơ bản để nắm thực hiện một thuật toán shuffle tiêu chuẩn với một twist nhỏ

Các quan sát quan trọng là cho 15 câu đố để có thể giải quyết được tính chẵn lẻ của các hoán vị và tính chẵn lẻ của hình vuông trống phải giống

Đầu tiên tạo ra một hoán vị ngẫu nhiên sử dụng một thuật toán tiêu chuẩn cho mục đích đó Ví dụ Knuth ngẫu nhiên thuật toán:.. Random hoán vị

Lợi thế của việc sử dụng shuffle của Knuth (hoặc Fisher-Yates shuffle) là nó liên quan đến việc trao đổi số, vì vậy bạn có thể dễ dàng theo dõi tính chẵn lẻ của hoán vị. Mỗi lần hoán đổi hoặc giữ chẵn lẻ (nếu bạn hoán đổi 1 & 3), hoặc thay đổi chẵn lẻ (nếu bạn hoán đổi 1 & 2).

Đặt hình vuông trống trên cùng một chẵn lẻ như độ chẵn lẻ của hoán vị và bạn đã hoàn tất. Nếu hoán vị có chẵn lẻ lẻ thì đặt một ô trống vuông (1,3,5, ... được chọn ngẫu nhiên). Nếu hoán vị có tính chẵn lẻ thì hãy để trống trên một hình vuông đều. ”

Ngoài ra," Thực tế, khoảng 4 hoán vị được tạo liên tiếp sẽ bao gồm hai hoán vị lẻ và thậm chí cả chi phí lặp lại không đáng kể "

Bạn cũng có thể kiểm tra trang web này ra:. http://eusebeia.dyndns.org/epermute

Answer 5

CẬP NHẬT ĐÁP:

Trước khi tôi giới thiệu thuật toán này, tôi cần phải xác định hai nhiệm kỳ. đảo ngược và cực

Đảo ngược: Một cặp đối tượng theo thứ tự ngược lại từ vị trí mà chúng cần phải có. Để biết thêm thông tin về đảo ngược, hãy tham khảo Counting inversions in an array

Phân cực của câu đố là liệu tổng số nghịch đảo trong tất cả các lát đều là lẻ hay lẻ. Một câu đố với 10 nghịch đảo thậm chí có cực; một câu đố với 7 nghịch đảo có cực kỳ lạ.

Xem xét câu đố 3x3 như sau:

| 6 | 3 | 2 |

| .. | 4 | 7 |

| 5 | 1 | 0 |

Đếm tất cả các đảo ngược ở đây, chúng tôi nhận được: (i) 6 được đảo ngược với 0, 1, 2, 3, 4 và 5. (ii) 3 được đảo ngược bằng 0, 1 và 2. (iii) 2 là đảo ngược với 0 và 1. (iv) 4 được đảo ngược với 0 và 1. (v) 7 được đảo ngược với 0, 1 và 5. (vi) 5 được đảo ngược bằng 0 và 1. (vii) 1 được đảo ngược bằng 0. Tổng cộng chúng tôi có số lần truy cập .

Nếu chiều rộng của câu đố thậm chí là số thì di chuyển một ô lên hoặc xuống sẽ đảo ngược cực sao cho điều quan trọng là câu đố có phân cực ngay cả khi ô trống nằm ở hàng cuối cùng.Đối với điều này, chúng tôi sẽ thêm khoảng cách của ô trống từ hàng cuối vào tổng số nghịch đảo của chúng tôi.

Bây giờ chúng ta biết rằng một câu đố có thể giải được là nó có tính phân cực (hoặc hoán vị). Vì vậy, nếu cực của chúng ta thì vấn đề của chúng ta được giải quyết nhưng đối với phân cực kỳ lạ chúng ta phải làm điều này:

Nếu ô trống không ở hàng đầu tiên, sau đó hoán đổi hai ô liền kề đầu tiên. Điều này sẽ thay đổi phân cực bằng 1 và chúng ta sẽ có câu đố có thể giải quyết được thậm chí là phân cực.

Nhưng nếu ô trống nằm ở hàng đầu tiên thì hãy hoán đổi các ô liền kề ở hàng cuối cùng. Điều này sẽ làm cho câu đố giải được. Vì vậy, vào cuối bạn luôn luôn kết thúc với một câu đố solvable.

Tôi hy vọng tôi đáp ứng các yêu cầu trả lời của stackoverflow cho câu hỏi này. Bất kỳ nghi ngờ được đánh giá cao. Cảm ơn bạn.