*GIẢI THUẬT IN CHỈNH HỢP KHÔNG LẶP CHẶP K CỦA N PHẦN TỬ • Nhắc lại chỉnh hợp : Chỉnh hợp lặp chặp K của N phần tử sẽ là tập hợp con bao gồm những phần tử của tập cha N. Ví dụ : tập N gồm { 1,2,3,4,5} thì chỉnh hợp không lặp chặp k = 3 là {1,2,3} hoặc { 2,3,4}. Chú ý : {1,1,2 } không thể coi là 1 chỉnh hợp không lặp được vì 1 và 1 là trùng nhau. • Cài đặt giải thuật : 1. Chúng ta sẽ có cấu hình đầu tiên là {1 2 3} và đi đến cấu hình cuối là {5,4,3}. Nhìn 1 cách tổng quát chúng ta thấy chẳng qua đây là kĩ thuật hoán vị nhưng là hoán vị 1 cách có lựa chọn. 2. Đầu tiên ta sẽ xét vị trí tại chặp k tức là A[k-1] với các phần tử sau chặp. Ví dụ : Tập n = 5 và k = 3 thì : 1 2 3 [4 5] thì tức là ta xét với các phần tử sau chặp ( 4,5 ). + Nếu vị trí hiện tại ( cuối cùng của chặp A[k-1] ) mà lớn hơn các phần tử sau chặp tức là nó đã gần như là cấu hình cuối của chập ( Vì sao tôi lại nói chữ gần ở đây, chúng ta sẽ khảo sát ở phần tiếp ). + Nếu vị trí hiện tại vẫn còn nhỏ hơn thì ta sẽ đỗi chỗ ( ở đây ta dùng kĩ thuật swap ) để hoán đổi. Ta lại được 1 cấu hình mới. Nếu không ta sẽ đến phần tử kế tiếp ( phần tử sau chặp ). Nghĩa là theo ví dụ trên nếu ta đã swap A[2] = 3 và A[3] = 4 rồi thì lần kế tiếp A[2] sẽ = 4 và A[3] = 3, tức là lần kế tiếp : 1 2 4 [3 5] Tới đậy rõ rang A[2] > A[3] thì ta sẽ xét phần tử kế tiếp A[4], nếu nhỏ hơn thì ta swap, còn không thì ta sẽ sang 1 vị trí mới của chặp tức là xét tới A[1]. 3. Nhưng liệu phần tử của chặp lớn hơn hết các phần tử sau chặp là cấu hình cuối hay không? Nhắc lại chữ “gần” mà tôi đã nói ở trện. Chúng ta sẽ xét them 1 ví dụ sau đây: 1 4 5 [2 3] Rõ rang là 4 > 2 và 3 nhưng nó vẫn < 5, vậy thì nó vẫn chưa thể là cấu hình cuối cùng được. Cho nên chúng ta phải xét tiếp vị trí hiện tai với các phần tử trong chặp nữa để bảo đảm chắc rằng nó là cấu hình cuối cùng. Chúng ta sẽ xét A[1] = 4 và A[2] = 5 : + Nếu A[1] > A[5] thì ta lại xét tiếp các phần tử kế tiếp trong chặp ( ví dụ : 1 6 7 8 [2 3 4 5]) ) + Nếu nhỏ hơn thì ta swap sau đó sắp xếp lại các phần tử tính từ vị trí đang xét cho đến cuối tập tức là A[n-1] thành giảm dần tức là ví dụ : 1 4 5 [2 3] thì ta sẽ swap A[1] và A[2] thành : 1 5 4 [2 3], nhưng nếu ta để như thế thì ta sẽ bỏ sót cấu hình 1 5 2 , 1 5 3….etc. cho nên đó là lý do tại sao tôi lại sắp xếp lại đoạn sau vị trí đang xét. Tức là : 1 5 2 3 4 Cứ thế chúng ta lại quay lại xét phần tử từ đầu chặp tức là lúc này là : 1 5 2 [3 4] cứ tiếp tục như thế đi cho đến cấu hình cuối cùng sẽ là 5 3 4 [1 2] • Code cài đặt bằng C++: #include #include const int size = 100; int A[size], Temp[size]; int number; int subset; int position; void swap ( int &r, int &c) { int temp = r; r = c; c = temp; } void Sort () { for(int a = position + 1; a < number-1; a++) for( int b = a+1; b < number; b++) if ( A[a] > A[b]) swap ( A[a], A[b] ); } void do_dec(int &position) { position--; if ( position >= 0 ) { Sort(); int k = position + 1; while ( k < number-1 ) { if ( A[k] < A[position] ) k++; else break; } if ( A[k] > A[position] ) swap( A[position], A[k] ); else do_dec(position); } } void main() { bool check; cout << " Enter the number array's elements need to be permutated: "; cin >> number; cout << " Enter subset : "; cin >> subset; for ( int i = 0; i < number; i++ ) A[i] = i+1; for ( int i = 0; i < number; i++ ) cout << A[i] << setw(5); cout << "\n\n"; cout << "-------permutation algorithm--------" << "\n\n"; do { for ( int i = 0; i < number; i++ ) { if ( i < subset ) cout << A[i] << "," << setw(5); else cout << "[" << A[i] << "]" << setw(3); } cout << "\n\n"; cin.get(); check = true; position = subset - 1; /* before subset 1 2 "3" [4 5], or the last index element of subset, 3 is an example with number = 5 and subset = 3 */ for ( int k = subset; k < number; k++ ) { if ( A[position] < A[k] ) check = false; } if ( check == false ) /* Check == false means there's still elements > than current position of subset so it's not a final configuration */ { if ( position >= 0 ) { /* check current posiont with the element after subset, if still not find one then increasing k */ int k = subset; while ( A[k] < A[position] ) k++; swap ( A[k], A[position] ); /*Found, swap with current position */ } } /*If there's no element greater than current position of subset, then check next position, position--*/ else do_dec(position); } while ( position >= 0 ); }