In tất cả các cách xếp n bạn nam và n bạn nữ vào 1 bàn tròn

#1

Hi mọi người, em là người mới học trong phần Giải thuật này. Hôm trước tìm thấy quyển sách của thầy Lê Minh Hoàng hay quá đem về học nhưng không có thầy cô hướng dẫn nên gặp chút khó khăn, mong mọi người giúp đỡ :smiley:
Đề bài như sau: Nhập vào danh sách n bạn nam và n bạn nữ, in ra tất cả các cách xếp 2n người đó vào một bàn tròn, mỗi bạn nam tiếp đến một bạn nữ (Sử dụng phương pháp sinh).
Em đang bí phần xây dựng thuật toán từ cấu hình x lên cấu hình x+1. Mọi người cho em ý tưởng và cách tư duy nhé, ko cần viết code cũng được.
Thanks mọi người.
P/s: Em là thành viên mới, rất vui được làm quen với mọi người.

#2

Trong một bàn tròn, mọi người có thể xoay vòng, nếu tất cả mọi người dịch k vị trí thì cấu hình không đổi.
Như vậy ta chọn 1 bạn bất kỳ làm mốc 0. Ví dụ bạn nam đầu tiên.
In ra tất cả các cách sắp xếp 2n-1 bạn còn lại trên 1 đường thẳng.

Mình mới nghĩ đến bước này. Mời bạn tiếp theo hỗ trợ :))

#3

Vẫn còn những trường hợp như kiểu a1b1a2b2 và a1b2a2b1 trùng nhau bạn ạ (a là nam, b là nữ). Như vậy nếu chọn 1 bạn làm mốc 0 thì vẫn có nhiều vấn đề phết :))

#4

Không trùng nhau bạn ạ, đó là flip chứ không phải rotate nữa rồi :))

#5

Ơ nhưng ngồi trên bàn tròn thì vẫn trùng mà nhỉ?

#6

Chỉnh hợp / tổ hợp??

1 Like
#7

Bạn không thể xoay abcd thành adcb được. Chỉ có thể thành bcda, cdab, dabc. Còn nếu tính cả flip thì bạn lấy tổng số kết quả chia cho 2, vì một cấu hình chỉ ảnh xạ đến 1 cấu hình flip và ngược lại

#8

Kí hiệu bạn nam thứ i là Bi (boy) và bạn nữ thứ j là Gj
Với số tự nhiên n > 0 cho trước, có n bạn nam là B1, B2, …, Bn, có n bạn nữ là G1, G2, …, Gn.
Bàn tròn ban đầu có n ghế.

Cách sắp xếp như sau, gồm các bước:

Bước 1: Sắp xếp các bạn nam.

  • Vì mỗi ghế trống trong bàn tròn tương đương nhau. Bạn nam B1 có thể chọn bất kì ghế nào trong bàn tròn. Số cách chọn cho B1 là 1.
  • Bàn tròn còn n-1 ghế, bạn nam B2 có n-1 cách chọn.
  • Bàn tròn còn n-2 ghế, bạn nam B3 có n-2 cách chọn.
  • …
  • Bàn tròn còn 2 ghế, bạn nam Bn-1 có 2 cách chọn.
  • Bàn tròn còn 1 ghế, bạn nam Bn có 1 cách chọn.

Vậy sắp xếp n bạn nam vào bàn tròn có tổng cộng (n-1)! cách.

Bước 2: Thêm n ghế đan xen

Tương ứng với mỗi cách sắp xếp ghế n bạn nam vào bàn tròn. Thêm n ghế đan xen giữa 2 bạn nam kế tiếp nhau:

  • Thêm n-1 ghế giữa 2 bạn nam Bi và Bi+1, với 1 <= i < n.
  • 1 ghế được thêm giữa bạn Bn và B0.

Bước 3: Sắp xếp n bạn nữ vào n ghế mới thêm vào

  • Bàn tròn còn n ghế, bạn nữ G1 có n cách chọn.
  • Bàn tròn còn n-1 ghế, bạn nữ G2 có n-1 cách chọn.
  • Bàn tròn còn n-2 ghế, bạn nữ G3 có n-2 cách chọn.
  • …
  • Bàn tròn còn 2 ghế, bạn nữa Gn-1 có 2 cách chọn.
  • Bàn tròn còn 1 ghế, bạn nữa Gn có 1 cách chọn.

Sắp xếp n bạn nữ vào n ghế được thêm vào có n! cách.

Tóm lại, có tổng cộng (n-1)!n! cách để sắp xếp n bạn nam và n bạn nữ vào bàn tròn.

Về giải thuật sinh, thay vì bạn Bi hay Gj có bao nhiêu cách chọn thì bạn có thể thay thành ghế thứ k có cách bạn nam Bm, Bn, Bp hay các bạn nữ Gm, Gn, Gp có thể được ngồi.
Riêng bước chọn của bạn B1 thì chọn bất kì trong n bạn nam làm gốc, thường chọn bạn ở vị trí 0 trong mảng chứa các bạn nam.

Cuối cùng, sử dụng backtracking algorithm và kĩ thuật đánh dấu mảng (trong sách LMH) để liệt kê từng hoán vị.

Khởi tạo dữ liệu:

  • Tạo mảng bool đánh dấu cho các bạn nam có n phần tử từ 0 đến n-1, giá trị ban đầu là false bvisited[n].
  • Tương tự mảng bool cho bạn nữ, là gvisited[n].
  • Tạo mảng int cho vị trí các bạn nam trong bàn tròn bchars[n]. Tương ứng ghế vị trí 0, 2, 4,…, 2n-2
  • Tạo mảng int cho vị trí các bạn nữ trong bàn tròn gchars[n]. Tương ứng ghế vị trí thứ 1, 3, 5, …, 2n-1
  • (Ghế được đánh số từ 0, 1, 2, 2n-1, trong đó vị trí chẵn của nam, vị trí lẻ của nữ)

Giải thuật:

  • Cho bạn nam số 0 vào ghế 0, bchars[0] = 0 và bvisited[0] = true.
  • Thực hiện giải thuật quay lui trên bchars và bvisited.
  • Với mỗi hoán vị của bchars, thực hiện tiếp giải thuật quay lui trên gchars và gvisited.
  • Với mỗi liệt kê thành công của bchars và gchars, in ra giá trị bchars[0], gchars[0], bchars[1], gchars[1],..., bchars[n-1], gchars[n-1].
3 Likes
#9 
# pseudo
require "combinatorics"
-> boys: [], girls: [];
for p in permutation(boys[1:-1]):
   for q in permutation(girls):
     print boys[0], *q.value.interleave(p.value);
     yield;
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?