生成符合給定約束條件的字串的所有排列

---

介紹

在本教程中，我們將使用 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 組合。在另一個示例中，使用了回溯法，它不會一次生成所有可能的組合。