Using backtracking to output all n number permutations that respect a condition

Question

I want to make an algorithm that reads the integers n, a and b and outputs all the permutations of n numbers where the numbers a and b are consecutive.

For example, if n=3, a=1, b=2 it should output 123 312.

I've used backtracking in order to find all n numbers permutations, but I don't know in what function and where I should put my condition, if that is even a thing.

void out()
{

   for (int i = 1; i <= n; ++i)
      cout << x[i];


   cout <<" ";
}

void back(int k)
{
   int i;
   for (i = 1; i <= n; ++i)
   {
      if (!p[i])
      {
         x[k] = i;
         p[i] = 1;
         if (k < n)
            back(k+1);
         else
            out();
         p[i] = 0;
      }
   }
}

Answer 1

Use standard algorithms to make your life easier. In particular, there is std::next_permutation to get all permutations. Then you can either follow the advice in a comment from Jarod42 and treat 12 as a single element. In that way any permutation has 1 and 2 adjacent:

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    int n = 5;
    int a = 1;
    int b = 3;

    std::vector<std::string> vec;
    for (int i=1; i <= n; ++i) if (i!=a && i!=b) vec.push_back(std::to_string(i));
    vec.push_back(std::to_string(a) + std::to_string(b));
    std::sort(vec.begin(),vec.end());
    
    std::vector<std::vector<std::string>> permutations;
    permutations.push_back(vec);
    while (std::next_permutation(vec.begin(),vec.end())) permutations.push_back(vec);

    for (const auto& permu : permutations) {
        for (const auto& e : permu) std::cout << e;
        std::cout << "\n";
    }
}

Alternatively, do not treat 12 as singe element and check the condition in the loop:

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    int n = 5;
    int a = 1;
    int b = 3;

    std::vector<int> vec;
    for (int i=1; i <= n; ++i) vec.push_back(i);
    
    std::vector<std::vector<int>> permutations;
    permutations.push_back(vec);
    while (std::next_permutation(vec.begin(),vec.end())) {
        if ( ... a is not adjacent to b ...) continue;
         permutations.push_back(vec);
    }

    for (const auto& permu : permutations) {
        for (const auto& e : permu) std::cout << e;
        std::cout << "\n";
    }
}

If you only need to print the permutations you need not store them in a vector, but print them directly.