«
»

Generating Permutations in C++

March 14, 2012, 1:15 am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <vector>
#include <iostream>
 
using namespace std;
 
void reverse(vector<int> &seq,int n1,int n2) {
 
  for(;(n2-n1)>=1;) {
    int temp = seq[n1]; seq[n1] = seq[n2]; seq[n2]=temp;
    n1++;
    n2--;
  }
 
}
 
int main() {
 
  int seq_len=4;
 
  vector<int> seq;
  for(int n=0;n<seq_len;n++) {seq.push_back(n);}
  for(int n=0;n<seq.size();n++) cout << seq[n] << " ";
  cout << endl;
 
  for(int n=0;n<seq_len;n++) {
 
    for(bool final=false;final==false;) {
 
      final=true;
      int k=0;
 
      for(int n=0;n<(seq.size()-1);n++) {
        if(seq[n] < seq[n+1]) {k=n; final=false;}
      }
 
      if(!final) {
        int l;
        for(int n=k+1;n<seq.size();n++) {
          if(seq[k] < seq[n]) {
            l=n;
          }
        }
 
        int temp = seq[k]; seq[k] = seq[l]; seq[l] = temp;
        reverse(seq,k+1,seq.size()-1);
        for(int n=0;n<seq.size();n++) cout << seq[n] << " ";
        cout << endl;
      }
    }
  }
}
Category: Uncategorized  |  Comment (RSS)  |  Trackback

Leave a Reply