C++ 生成符合给定约束条件的字符串的所有排列

在本教程中，我们使用C++编程概念实现两个示例，生成输入字符串的所有排列。字符串的排列是通过交换字符位置来排列字符串的方式的数量。我们还包含一些限制或限制条件。输入字符串的所有排列或排列都确保字符B不会跟随字符A的任何地方，意味着字符串中没有AB的组合。

为了实现这个任务，我们使用了两种方法：

直接生成满足AB限制条件的字符串的所有组合。
使用回溯法。

示例1

String = “ACB”

输出

BAC, CBA, BCA

在上面的演示中，使用输入字符串的限制是字符串排列中没有AB的组合。可能的排列数有BAC、CBA和BCA。

示例2

String = “BDC”

输出

BCD, DCB, DBC, BDC, CBD, CDB

在上面的演示中，输入字符串中没有A。该字符串可以生成所有可能的排列，这些排列是BCD、DCB、DBC、BDC、CBD和CDB。

示例3

String = “ABD”

输出

ADB, DBA, BDA, BAD

在上述示例中，输入字符串是“ABD”，约束是B在任何字符串排列中不跟随A。考虑到这个约束，生成的输入字符串排列的可能数量是ADB、DBA、BDA和BAD。

步骤

获取输入字符串。
使用库函数permute()生成所有可能的排列。
使用find()函数进行约束。
使用for循环递归生成具有约束的所有排列。
打印所有生成的输入字符串的排列。

语法

find()： 这是在string头文件中定义的字符串类库函数。它用于在输入字符串中搜索特定元素，并返回搜索元素的第一个索引值。

string_name.find(value);

permute() :

这个C++库函数生成字符串的可能排列。它接受两个参数，定义不同字符串组合的开始和结束。

string_name.permute(first, end);

swap() ： 它是一个在<std>头文件中定义的标准库函数。它用于交换两个值。

swap(varaible_1, varaible_2);

示例 1

我们使用输入字符串“ACB”实现一个例子。使用递归来生成从开始到结束的所有可能的排列。使用find()函数从字符串中删除AB组合。在字符串npos中，字符串的值被打印到最后。

#include <bits/stdc++.h>
using namespace std;

void permute(string& s, int m, int a)
{

  //checking validity of current permutation
    if (m == a) 
    {
        if (s.find("AB") == string::npos)
            cout << s << " ";
        return;
    }

    // generating all possible permutation
    for (int x = m; x <= a; x++)
    {
        swap(s[m], s[x]);
        permute(s, m + 1, a);
        swap(s[m], s[x]);
    }
}

int main()
{
    string s = "ACB";
    permute(s, 0, s.length() - 1);
    return 0;
}

输出

ACB CBA BCA BAC

示例 2

为了实现这个例子，我们使用回溯法。在上述的实现中，我们生成所有的排列，然后函数将移除约束条件。这种方法很耗时，通过使用回溯法，我们并没有生成所有的排列，而是在考虑删除AB的情况下生成排列。

#include <bits/stdc++.h>
using namespace std;

bool permuteString(string& s, int m, int j, int a)
{
//removing A and B from recursion
    if (m != 0 && s[m - 1] == 'A' && s[j] == 'B')
        return false;

    // Remove AB combination or swapping with BA
    if (a == m + 1 && s[j] == 'A' && s[m] == 'B'
        || a == m + 1 && m == j && s[a] == 'B'
               && s[m] == 'A')
        return false;

    return true;
}

void permute(string& s, int m, int a)
{
     if (m == a) 
    {
        cout << s << " ";
        return;
    }

     for (int x = m; x <= a; x++)
    {

        if (permuteString(s, m, x, a)) 
        {
            swap(s[m], s[x]);
            permute(s, m + 1, a);
            swap(s[m], s[x]);
        }
    }
}

//Controller
int main()
{
    string s = "ACB";

    // calling function
    permute(s, 0, s.length() - 1);
    return 0;
}