使用回溯来输出符合条件的所有 n 个数字排列

Question

我想做一个算法，读取整数 n、a 和 b，并输出 n 个数字的所有排列，其中数字 a 和 b 是连续的。

例如，如果 n=3，a=1，b=2，它应该输出 123 312。

我使用回溯来找到所有 n 个数字排列，但我不知道应该在哪个函数中以及在哪里放置我的条件，如果那是一件事的话。

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

使用标准算法让您的生活更轻松。特别是，有 std::next_permutation 来获取所有排列。然后，您可以遵循 Jarod42 评论中的建议，并将 12 视为单个元素。这样，任何排列都有 1 和 2 相邻：

#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";
    }
}

或者，不要将 12 视为单个元素并检查循环中的条件：

#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您只需要打印排列，不需要将它们存储在向量中，而是直接打印它们。