fork download
copy 
  1. #include <iostream>
  2. #define FIN "permutari.in"
  3. #define FOUT "permutari.out"
  4. #define SIZE 100
  5.  
  6. using namespace std;
  7.  
  8. int stack[ SIZE ],//pastreaza solutiile /permutarile
  9.     level,
  10.     n;//card
  11.  
  12. void init() {
  13.  
  14.     stack[level ] = 0;
  15. }
  16.  
  17. int succ() {
  18.  
  19.      if(stack[ level ] < n) {
  20.  
  21.         stack[level]++;
  22.  
  23.         return 1;
  24.      }
  25.  
  26.      return 0;
  27. }
  28.  
  29.  
  30. int valid() {
  31.  
  32.     for(int i = 1; i < level; ++i) {
  33.  
  34.          if(stack[level] == stack[i]) return 0;
  35.     }
  36.  
  37.     return 1;
  38.  
  39. }
  40.  
  41. void display_solution() {
  42.  
  43.      for(int i = 1; i <= n; ++i) {
  44.  
  45.         cout<<stack[i]<<" ";
  46.      }
  47.  
  48.      cout<<endl;
  49. }
  50.  
  51. int sol() {
  52.  
  53.     return level == n;
  54. }
  55.  
  56. //iterativ
  57. void backtracking() {
  58.  
  59.      int s, v;
  60.  
  61.      level = 1;
  62.  
  63.      while( level > 0) {
  64.  
  65.             s = 1; v = 0;
  66.  
  67.             while( s && !v ) {
  68.  
  69.                 s = succ();
  70.  
  71.                 if( s ) {
  72.  
  73.                    v = valid();
  74.                 }
  75.             }
  76.  
  77.             if( s ) {
  78.                      if( sol() ) {
  79.  
  80.                        display_solution();
  81.  
  82.                      } else {
  83.  
  84.                        level++;
  85.  
  86.                        init();
  87.                      }
  88.             } else {
  89.  
  90.               level--;
  91.             }
  92.      }
  93. }
  94.  
  95.  
  96. int main(int argc, char const *argv[]) {
  97.  
  98.  
  99.     //ifstream fin("fisier.txt");
  100.  
  101.     //freopen(FIN, "r", stdin);
  102.     //freopen(FOUT, "w", stdout);
  103.  
  104.    //n = 3
  105.    //A = { 1, 2, 3 }
  106.    //A = {"audi","car","bmw"}
  107.  
  108.     cin>>n;
  109.  
  110.     backtracking();
  111.  
  112.   return 0;
  113. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
3
stdout
copy 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1
https://ideone.com/J5acy7
Permutari - iterative - ATP
language:
C++ (gcc 8.3)
created:
37 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!