Thuật toán sinh(Generation)

1. Điều kiện áp dụng
   1. Biết được cấu hình đầu tiên và cuối cùng của bài toán. Xác định được thứ tự các cấu hình cần liệt kê của bài toán
   2. Từ một cấu hình đã biết, Ta xây dựng được cấu hình kế tiếp dựa vào cấu hình đã biết đó theo quy tắc nào đó
2. Mô hình
   Thuật toán Generation:
   Bước 1 (Khởi tạo):
     < khởi tạo cấu hình đầu tiên>
   Bước 2 (Lặp)
     While(Khi chưa phải cấu hình cuối cùng) do:
       < Đưa ra cấu hình hiện tại>
       < Sinh cấu hình tiếp theo>
     EndWhile
3. Bài toán điển hình
   1. Sinh xâu nhị phân
      Ví dụ:
      input: 3
      output: 000,001,010,011,100,101,110,111
      Code:

          #include < iostream >
          using namespace std;
          bool ok= true;
          int X[100];
          int n;
          void result(){
              for(int i=1;i<=n;i++)
              cout << X[i];
              cout << endl;
          }
          void next_bit_string(){
              int i=n;
              while(i>0 && X[i]!=0){
                  X[i]=0;i--;
              }
              if(i>0) X[i]=1;
              else ok=false;
          }
          int main(){
              //Khoi tao
              cin>>n;
              for(int i=0;i < =n;i++)
                  X[i]=0;
                                      
              //lap
              while(ok){
                  result();
                  next_bit_string();
              }
          }
          

   2. Sinh tổ hợp
      Ví dụ: Sinh tổ hợp chập k của n
      input: 4 3
      output: 123,124,134,234
      Code:

          #include
          using namespace std;
          bool ok=true;
          int n,k;
          int X[100];
          void result(){
              for(int i=1;i<=k;i++)
              cout << X[i];
              cout << endl;
          }
          void Next_Combination(){
              int i=k;
              while(i>0&&X[i]==n+i-k){
                  i--;
              }
              if(i>0){
                  X[i]=X[i]+1;
                  for(int j=i+1;j<=k;j++){
                      X[j]=X[i]+j-i;
                  }
              }
              else ok=false;
          }
          int main()
          {
              //Khoi tao
              cin>>n>>k;
              for(int i=1;i<=k;i++)
                  X[i]=i;
              //lap
              while(ok){
                  result();
                  Next_Combination();
              }
          }
                          

   3. Sinh hoán vị
      Ví dụ: Sinh tổ hợp chập k của n
      input: 3
      output: 123,132,213,231,312,321
      Code:

          //Hoan vi
          #include
          using namespace std;
          bool ok = true;
          int X[100];
          int n;
          void result(){
           for(int i=1;i<=n;i++)
            cout << X[i];
           cout << endl;
          }
          void Next_Permutation(){
           int j=n-1;
           while(j>0&&X[j]>X[j+1]) j--;
           if(j>0){
            int k=n;
            while(X[j]>X[k]) k--;
            int t=X[j];X[j]=X[k];X[k]=t;
            int r=j+1,s=n;
            while(r<=s)
            {
             t=X[r];X[r]=X[s];X[s]=t;
             r++;s--;
            }
           }
           else ok=false;
          }
          int main()
          {
           //Khoi tao
           cin>>n;
           for(int i=1;i<=n;i++)
               X[i]=i;
           while(ok){
            result();
            Next_Permutation();
           }
          }