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

---

介绍

在本教程中，我们将使用 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”实现一个示例。应用字符串 npos 使用递归生成所有可能的排列直到结尾。使用 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;
}

输出

ACB CBA BCA BAC 

结论

我们完成了本教程，该教程在考虑 AB 不一起出现这一约束的同时生成所有可能的排列。使用不同的方法实现了 2 个示例来解决任务，并使用 3 个演示进行了描述。

使用递归方法，我们生成了所有可能的排列，然后从结果中删除了 AB 组合。在另一个示例中，使用了回溯法，它不会一次生成所有可能的组合。