kburnik

C++ - Permutacija 1 - 6 elemenata rekurzivno

Dec 1st, 2012
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Zadatak: Permutacija od 1 do 6 elemenata rekurzivno
  3.  
  4.     Datum: 2012-12-01
  5.  
  6.     Autor: Kristijan Burnik, udruga informatičara Božo Težak
  7.  
  8.     Gmail: kristijanburnik
  9.  
  10. */
  11. #include <iostream>
  12. #include <cstdlib>
  13. #include <vector>
  14.  
  15.  
  16. using namespace std;
  17.  
  18. void ispisi(vector <int> &v) {
  19.     int n = v.size();
  20.     for (int i = 0; i < n; i ++){
  21.         cout << v[i] << " ";    
  22.     }    
  23.     cout << endl;
  24. }
  25.  
  26.  
  27. // prouciti ovu proceduru,
  28. // iz nje nastaje uzorak po kojem gradimo permutacije za bilo koji broj elemenata
  29. void permutiraj_do_6_elemenata ( vector<int> & v, int pocetak, int kraj ) {
  30.        int n = kraj - pocetak+1;
  31.        if (n == 1) {
  32.             ispisi(v);
  33.             return;
  34.        }      
  35.        if (n == 2) {
  36.             // permutiraj bez pocetne zamjene
  37.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  38.            
  39.             // zamijeni i permutiraj
  40.             swap(v[pocetak],v[pocetak+1]);  // (trenutni sa 1. susjedom)
  41.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  42.            
  43.             // vrati natrag poredak
  44.             swap(v[pocetak],v[pocetak + 1]);
  45.            
  46.             return;
  47.        }
  48.        if (n == 3) {
  49.            
  50.             // permutiraj bez pocetne zamjene
  51.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  52.            
  53.             // zamijeni i permutiraj            
  54.             swap(v[pocetak],v[pocetak+1]); // (trenutni sa 1. susjedom)
  55.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  56.            
  57.             swap(v[pocetak],v[pocetak+2]); // (trenutni sa 2. susjedom)
  58.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  59.  
  60.            
  61.             // vrati natrag poredak
  62.             swap(v[pocetak],v[pocetak+2]);
  63.             swap(v[pocetak],v[pocetak+1]);
  64.            
  65.             return;
  66.       }
  67.       if (n == 4) {
  68.            
  69.             // permutiraj bez pocetne zamjene
  70.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  71.            
  72.             // zamijeni i permutiraj
  73.             swap(v[pocetak],v[pocetak+1]); // (trenutni sa 1. susjedom)          
  74.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);  
  75.            
  76.             swap(v[pocetak],v[pocetak+2]); // (trenutni sa 2. susjedom)          
  77.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  78.  
  79.             swap(v[pocetak],v[pocetak+3]); // (trenutni sa 3. susjedom)          
  80.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);  
  81.            
  82.             // vrati natrag poredak
  83.             swap(v[pocetak],v[pocetak+3]);
  84.             swap(v[pocetak],v[pocetak+2]);
  85.             swap(v[pocetak],v[pocetak+1]);
  86.            
  87.             return;
  88.       }
  89.      
  90.       if (n == 5) {
  91.            
  92.             // permutiraj bez pocetne zamjene
  93.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  94.            
  95.             // zamijeni i permutiraj
  96.             swap(v[pocetak],v[pocetak+1]); // (trenutni sa 1. susjedom)
  97.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  98.            
  99.             swap(v[pocetak],v[pocetak+2]); // (trenutni sa 2. susjedom)          
  100.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  101.  
  102.             swap(v[pocetak],v[pocetak+3]); // (trenutni sa 3. susjedom)
  103.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);  
  104.  
  105.             swap(v[pocetak],v[pocetak+4]); // (trenutni sa 4. susjedom)
  106.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);  
  107.            
  108.             // vrati natrag poredak
  109.             swap(v[pocetak],v[pocetak+4]);
  110.             swap(v[pocetak],v[pocetak+3]);
  111.             swap(v[pocetak],v[pocetak+2]);
  112.             swap(v[pocetak],v[pocetak+1]);
  113.            
  114.             return;
  115.       }
  116.      
  117.       if (n == 6) {
  118.             // permutiraj bez pocetne zamjene
  119.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  120.            
  121.             // zamijeni i permutiraj
  122.             swap(v[pocetak],v[pocetak+1]); // (trenutni sa 1. susjedom)
  123.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  124.            
  125.             swap(v[pocetak],v[pocetak+2]); // (trenutni sa 2. susjedom)          
  126.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);            
  127.  
  128.             swap(v[pocetak],v[pocetak+3]); // (trenutni sa 3. susjedom)
  129.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);  
  130.  
  131.             swap(v[pocetak],v[pocetak+4]); // (trenutni sa 4. susjedom)
  132.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  133.  
  134.             swap(v[pocetak],v[pocetak+5]); // (trenutni sa 5. susjedom)
  135.             permutiraj_do_6_elemenata(v,pocetak+1,kraj);
  136.            
  137.             // vrati natrag poredak
  138.             swap(v[pocetak],v[pocetak+5]);
  139.             swap(v[pocetak],v[pocetak+4]);
  140.             swap(v[pocetak],v[pocetak+3]);
  141.             swap(v[pocetak],v[pocetak+2]);
  142.             swap(v[pocetak],v[pocetak+1]);
  143.            
  144.             return;
  145.       }
  146. }
  147.  
  148. int main(void) {
  149.  
  150.     int n;
  151.     cin >> n;
  152.    
  153.     if (n > 6) {
  154.             cout << "Ne moze vise od 6 elemenata!" << endl;
  155.             system("pause");
  156.             return 0;
  157.     }
  158.  
  159.     vector<int> v;
  160.     v.resize(n);
  161.     for (int i = 0; i < n ; i++) {
  162.         cin >> v[i];
  163.     }
  164.    
  165.     permutiraj_do_6_elemenata(v,0,n-1);
  166.  
  167.  
  168.  
  169.     system("pause");
  170.     return 0;
  171. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×