Thuật toán sinh

Sơ lược thuật toán

• Xác định thứ tự từ điển, cấu hình đầu và cuối
• Xác định thuật toán sinh kế tiếp
• Sinh cấu hình đầu tiên, cho đến khi chưa phải cấu hình cuối cùng, sinh cấu hình kế tiếp

Ứng dụng

Bài toán sinh dãy nhị phân độ dài n

• Đặt , với
• Gọi N là số thập phân tương ứng với xâu nhị phân , N’ là số thập phân tương ứng với xâu nhị phân .
• Thứ tự từ điển: trước nếu N < N’.
• Cấu hình đầu tiên: ( số 0)
• Cấu hình cuối cùng: ( số 1)
• Thuật toán sinh kế tiếp:
  • Xét từ phải sang trái, tìm chữ số đầu tiên sao cho
  • ; với
  • Ví dụ: 00110 → 00111 → 01000

Bài toán sinh tổ hợp chập k của n phần tử

• Xét tập hợp n số tự nhiên đầu tiên
• Tổ hợp chập k của n phần tử có dạng với
• Thứ tự từ điển: trước nếu tồn tại sao cho và
• Cấu hình đầu tiên:
• Cấu hình cuối cùng:
• Thuật toán sinh kế tiếp
  • Xét từ phải sang trái, tìm vị trí đầu tiên sao cho
  • ; với
  • Ví dụ với

Bài toán sinh hoán vị của n phần tử

• Xét tập hợp n số tự nhiên đầu tiên
• Một hoán vị có dạng với và
• Thứ tự từ điển: tương tự chỉnh hợp
• Cấu hình đầu tiên:
• Cấu hình cuối cùng:
• Thuật toán sinh kế tiếp
  • Tính từ phải qua trái, tìm vị trí đầu tiên sao cho
  • Tìm vị trí sao cho nhỏ nhất, lớn hơn
  • Đổi chỗ và
  • Lật ngược đoạn đến
  • Ví dụ: ,