Chỉnh hợp không lặp

Permutation without repetition Cho một tập N phần tử khác nhau. Hãy liệt kê tất cả các khả năng tập k phần tử từ tập N sao cho không có phần tử nào lặp lại. Ví dụ: Tập {1, 2, 3, 4} chỉnh hợp không lặp 2 phần tử sẽ gồm

• {A, B}, {A, C}, {A, D}
• {B, A}, {B, C}, {B, D}
• {C, A}, {C, B}, {C, D}
• {D, A}, {D, B}, {D, C}

$$P_n^k=\;n(n-1)(n-2)...(n-k+1)=\frac{n!}{(n-k)!}$$ P là viết tắt của từ Permutation, hoán vị. Với $$P_4^2 = \frac{4!}{(4-2)!} = 3 * 4 = 12$$

Hoán vị

Hoán vị là trường hợp đặc biệt của chỉnh hợp không lặp với k = n $$P_n^n= {n!}$$

Ví dụ cụ thể

Cho một mảng 6 ký tự {'A', 'B', 'C', 'D', 'E', 'F'} hãy liệt kê chỉnh hợp không lặp có độ dài 3 phần tử từ nguồn là mảng ban đầu.

Data structure:

1. Định nghĩa mảng lưu tập N phần tử: char source[] = "ABCDEF";
2. Định nghĩa một mảng có k phần tử: char array[k] để chứa các khả năng sắp xếp

Algorithm: