字串的排列，使得其中字元的數量大於其相鄰字元的數量的最大化

在各種解決問題的場景中操作字串至關重要。發現給定字串的排列可以優化大於相鄰字元的字元數，這是一個有趣的難題，需要重新排列字串的字元以產生盡可能多的相鄰字元對，其中左側字元小於右側字元。 p>

方法

有多種方法可以解決字串的排列，其中最大字元數大於與其直接相鄰的字元數。

方法 1 − 回溯法與剪枝 −

#方法 2 - 動態規劃 -

方法3 - 堆演算法-

方法 4 - 修剪的字典順序 -

方法一：回溯法與剪枝

• 使用回溯演算法產生字串的所有排列。

• 在每個步驟中，檢查當前排列是否有比其相鄰字元更多的字元大於迄今為止找到的最大值。

• 如果沒有，請儘早修剪分支並回溯以避免不必要的計算。

文法

function backtrack_permutation(string):
   n = length(string)
   max_count = [0]  

• 儲存大於相鄰字元的最大字元數

result = [None] * n 

• 儲存最終排列

#

function backtrack(curr_permutation, used_chars):
nonlocal max_count
if length(cu permutation) == n:

• 計算大於相鄰字元的字元數量

count = 0
   for i in range(1, n - 1):
      if cu permutation [i - 1] < cu permutation[i] > cu permutation [i + 1]:
   count += 1
      if count > max count [0]:
      max count [0] = count
      result [:] = cu permutation  

• 更新結果

return
   for i in range(n):
      if not used_chars[i]:

• 選擇下一個字元

#

used_chars[i] = true
curr_permutation.append(string[i])

• 回溯到下一個位置

backtrack(curr_permutation, used_chars)

• 撤銷選擇

used_chars[i] = false
curr_permutation.pop()

• 開始回溯過程

#

used_chars = [false] * n 

• 追蹤已使用的字元

#

curr_permutation = []
backtrack(curr_permutation, used_chars)

return result.

演算法

步驟 1 - 用空字串開始 max_permutation。

• 應定義輔助函數回溯（current_permutation、remaining_characters）。

步驟2 - 如果字串remaining_characters為空 -

• 如果目前排列的長度比最大排列的長度長，將max_permutation設定為current_permutation。

• 返回。

步驟 3 - 在迭代中，遍歷剩餘字元中的每個字元 c -

• 將 c 加入到 current_permutation 中以建立 new_permutation。

• 如果new_permutation的長度大於1且其最後一個字符不再長於其前面的字符，則跳過此迭代。

• 從remaining_characters中取出c，產生新的new_remaining。

• 迭代呼叫回溯（new_permutation、new_remaining）。

第四步 - 呼叫回溯函數，將輸入文字作為remaining_characters，將空字串作為current_permutation。

第 5 步 - 提供輸出 max_permutation。

範例 1

此程式透過首先將輸入字串「abcd」按升序排列來操作。隨後，使用回溯函數產生每個可能的排列，該函數僅考慮大於前一個字符的字符，從而避免了不符合條件的重複排列。此外，isValidPermutation函數根據每個字元與其前一個字元進行評估，對於任何等於或小於後者的情況傳回false。

結果是，這個有目的的過程會創建所有有效的排列，其中每個字元的最大數量都高於其相鄰字元。我們可以自由地進一步定制給定的輸入字串、代碼和邏輯，以滿足個人的要求。

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

using namespace std;
int maxCount = 0;

bool isValidPermutation(const string& str) {
   for (int i = 1; i < str.length(); i++) {
      if (str[i] <= str[i - 1]) {
         return false;
      }
   }
   return true;
}

void backtrack(string& str, int pos) {
   if (pos == str.length()) {
      if (isValidPermutation(str)) {
         cout << str << endl;
      }
      return;
   }

   for (int i = pos; i < str.length(); i++) {
      swap(str[pos], str[i]);
      if (str[pos] > str[pos - 1]) {
         backtrack(str, pos + 1);
      }
      swap(str[pos], str[i]);
   }
}

int main() {
   string input = "abcd";
   sort(input.begin(), input.end());  // Sort the input string initially
   backtrack(input, 1);

   return 0;
}

輸出

abcd

方法二：動態規劃

• 使用動態規劃逐步產生字串的排列。

• 從空前綴開始，考慮所有可能的位置，並迭代地向其中添加字元。

• 維護目前前綴中大於其相鄰字元的字元數。

• 修剪計數已經低於目前發現的最大值的分支。

文法

def find_max_permutation(string):
   n = len(string)
   dp = [0] * n
   dp[0] = 1

• 動態程式設計循環

#

for i in range (1, n):

• 檢查目前字元是否大於其相鄰字元

if string[i] > string[i-1]:

• 如果是，則將計數增加1

dp[i] = dp[i-1] + 1
else:

• 如果不是，計數是相同的

dp[i] = dp[i-1]

• 找出 dp 陣列中的最大計數

max_count = max(dp)

return max_count

演算法

步驟 1 - 建立一個名為 maxPerm(str) 的函數，接受字串作為輸入，並傳回滿足指定條件的最長字串的排列。

步驟 2 - 首先初始化長度為 n 的陣列（稱為 dp），其中 n 等於輸入字串 str 的長度。以位置 i 結束的最大排列字串儲存在每個元素 dp[i] 中。

第三步 - 將 dp [0] 初始化為字串 str 的第一個字元。

第四步 - 從索引1到n-1迭代遍歷str的字元 -

• 初始化一个空字符串curr来存储当前最大排列字符串。

• 对于索引 i 处的每个字符，将其与索引 i-1 处的前一个字符进行比较。

• 如果 str[i] 大于 str[i-1]，将 str[i] 添加到 curr 中。

• 否则，将 str[i-1] 追加到 curr 中。

• 使用 dp[i-1] 和 curr 之间的最大值更新 dp[i]。

第5步 - 循环完成后，最大排列字符串将存储在dp[n-1]中。

第 6 步 - 返回 dp[n-1] 作为结果。

Example 2

的中文翻译为：

示例2

在此示例中，输入字符串被硬编码为“abcbdb”。 findMaxPermutation 函数使用动态编程来计算每个索引处大于其相邻字符的最大字符数。然后，它通过回溯表来重建具有最大计数的字符串。生成的最大排列在 main 函数中打印。

#include <iostream>
#include <string>
#include <vector>

std::string findMaxPermutation(const std::string& str) {
   int n = str.length();
    
   // make a table to store the maximum count of characters
   // larger than their adjacent characters
   std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));

   // Initialize the table for the base case
   dp[0][0] = 0; // Count when str[0] is not included
   dp[0][1] = 1; // Count when str[0] is included
    
   // Calculate the maximum count for each index
   for (int i = 1; i < n; i++) {
      // When str[i] is not involved, the count is the maximum
      // when str[i-1] is included or not 
      dp[i][0] = std::max(dp[i-1][0], dp[i-1][1]);
        
      // When str[i] is involved, the count is the count when
      // str[i-1] is not included plus 1
      dp[i][1] = dp[i-1][0] + 1;
   }
    
   // The more count will be the largest of the last two values
   int maxCount = std::max(dp[n-1][0], dp[n-1][1]);

   // Reconstruct the string with the maximum count
   std::string maxPerm;
   int i = n - 1;
   int count = maxCount;
    
   // Start from the end and check which character to include
   while (i >= 0) {
      if ((dp[i][0] == count - 1 && dp[i][1] == count) || (dp[i][0] == count && dp[i][1] == count)) {
         maxPerm = str[i] + maxPerm;
         count--;
      }
      i--;
   }
   return maxPerm;
}
int main() {
   std::string str = "abcbdb";
   std::string maxPerm = findMaxPermutation(str);
    
   std::cout << "String: " << str << std::endl;
   std::cout << "Max Permutation: " << maxPerm << std::endl;
    
   return 0;
}

输出

String: abcbdb
Max Permutation: bbb

方法三：堆算法

• 实现Heap算法，高效地生成字符串的所有排列。

• 生成每个排列后，计算大于其相邻字符的字符数量。

• 保持追踪到目前为止找到的最大计数，并根据需要进行更新。

语法

function generatePermutations(string):
   n = length(string)
   characters = array of n elements initialized with string's characters

   generatePermutationsHelper(n, characters)

function generatePermutationsHelper(n, characters):
   if n = 1:
      checkAndPrintPermutation(characters)
   else:
   for i = 0 to n-1:
      generatePermutationsHelper(n-1, characters)
            
   if n is even:
      swap characters[i] and characters[n-1]
   else:
      swap characters [0] and characters[n-1]

算法

第一步 - 已经初始化了一个数组，用于存储输入字符串的字符。

第 2 步 - 继续创建一个函数，并将其命名为“generatePermutations”，带有两个参数 - 一个最终变量“size”，用于确定数组的大小，以及一个名为“arr”的数组，其中包含字符串字符。

步骤 3 - 如果大小为 1，则通过将数组中的字符组合在一起，直到最大字符数超过连续字符数，打印当前排列。

步骤 4 - 如果不是，则函数返回。为了从索引 0 到 'size - 1' 迭代数组，我们使用一个名为 'i' 的变量。

第 5 步 - 在此迭代中，我们进一步迭代参数大小 - 1 和错误的generatePermutations 函数。

第 6 步 - 如果 size 恰好是奇数，则我们将数组中索引 0 处的元素替换为索引“size - 1”处的元素。

第 7 步 - 类似地，如果 size 结果是偶数，我们将数组中索引“i”处的元素替换为索引“size - 1”。

步骤8 - 最后，我们使用初始数组大小和数组本身作为参数调用"generatePermutations"函数。

示例 1

以下的C++示例使用Heap's算法创建字符串的排列，并识别出在其相邻字符上具有最大字符数的排列 −

为了说明问题，在这个例子中使用"abcd"作为输入字符串。可以修改变量来使用不同的输入字符串。如果排列满足具有比其邻居更多字符的要求，则找到isValidPermutation函数是否有效。generatePermutations函数使用堆栈方法来跟踪具有最多字符的排列，以便它可以生成输入字符串的每个可能的排列。主函数将最大数量和排列本身作为输出打印。

#include <iostream>
#include <algorithm>
using namespace std;

// Function to check if the permutation satisfies the condition
bool isValidPermutation(const string& perm) {
   int n = perm.length();
   for (int i = 0; i < n - 1; i++) {
      if (abs(perm[i] - perm[i + 1]) <= 1)
         return false;
   }
   return true;
}

// Function to swap two characters in a string
void swapChar(char& a, char& b) {
   char temp = a;
   a = b;
   b = temp;
}

// Heap's Algorithm for generating permutations
void generatePermutations(string& str, int n, int& maxCount, string& maxPerm, int idx = 0) {
   if (idx == n - 1) {
      if (isValidPermutation(str)) {
         int count = count_if(str.begin(), str.end(), [](char c) {
            return isalpha(c) && c >= 'A' && c <= 'Z';
         });
         if (count > maxCount) {
            maxCount = count;
            maxPerm = str;
         }
      }
      return;
   }

   for (int i = idx; i < n; i++) {
      swapChar(str[idx], str[i]);
      generatePermutations(str, n, maxCount, maxPerm, idx + 1);
      swapChar(str[idx], str[i]);
   }
}

int main() {
   string str = "abcd";
   int n = str.length();
   int maxCount = 0;
   string maxPerm;

   generatePermutations(str, n, maxCount, maxPerm);

   if (maxCount == 0) {
      cout << "No valid permutation found." << endl;
   } else {
      cout << "Maximum number of characters greater than adjacent characters: " << maxCount << endl;
      cout << "Permutation with the maximum count: " << maxPerm << endl;
   }
   return 0;
}

输出

No valid permutation found.

方法4：字典序排序与剪枝

• 按字典顺序对字符串的字符进行排序。

• 生成排序字符串的排列。

• 在每一步中，检查当前排列是否满足最大字符数大于其相邻字符的条件。

• 如果不是这样，请跳过具有相似前缀的剩余排列，以避免不必要的计算。

语法

• 生成字符串所有排列的函数

function generatePermutations(string):

• TODO：排列生成的实现

• 检查字符是否大于其相邻字符的函数

function isGreaterAdjacent(char1, char2):

• TODO：比较逻辑的实现

• 找到具有大于相邻字符的最大数量的排列的函数

function findMaxAdjacentPermutation(string):

• 生成字符串的所有排列

permutations = generatePermutations(string)

• 初始化变量

max_permutation = ""
max_count = 0

• 遍历每个排列

for permutation in permutations:
   count = 0

• 迭代排列中的每个字符（不包括最后一个字符）

for i from 0 to length(permutation) - 2:
   char1 = permutation[i]
   char2 = permutation[i + 1]

• 检查当前字符是否大于其相邻字符

if isGreaterAdjacent(char1, char2):
   count = count + 1

• 检查当前排列的计数是否大于先前的最大值

if count > max_count:
   max_permutation = permutation
   max_count = count

• 返回具有最大计数的排列

return max_permutation

算法

第一步 - 从输入字符串开始。

第 2 步 - 按字典顺序对字符串进行排序以获得初始排列。

第 3 步 - 将变量 maxCount 初始化为 0，以跟踪大于相邻字符的最大字符数。

第 4 步 - 初始化变量 maxPermutation 以存储最大计数的排列。

第 5 步 - 当有下一个排列时 -

• 将变量 count 初始化为 0，以跟踪当前大于相邻字符的字符数。

• 对于当前排列中的每个字符 -

  • 检查当前字符是否大于其前一个字符和后一个字符（如果存在）。

  • 如果满足条件，则将计数增加 1。

• 如果计数大于最大计数（maxCount）-

  • 将maxCount更新为当前计数。

  • 将 maxPermutation 更新为当前排列。

步骤 6 - 将 maxPermutation 作为结果返回。

示例 1

对于此示例，为简单起见，让我们考虑固定字符串“abcde”。

在这个例子中，countAdjacentGreater函数统计字符串中相邻字符大于其前一个字符的数量。findMaxPermutation函数生成输入字符串的所有排列，并检查每个排列，找出具有最大数量相邻字符大于的那个。

主要函数初始化输入字符串"abcde"和跟踪最大计数和最大排列的变量。它调用findMaxPermutation函数来找到最大排列。

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

using namespace std;

int countAdjacentGreater(const string& str) {
   int count = 0;
   for (int i = 0; i < str.length() - 1; i++) {
      if (str[i] < str[i + 1]) {
         count++;
      }
   }
   return count;
}

void findMaxPermutation(string& str, int& maxCount, string& maxPerm) {
   sort(str.begin(), str.end());
    
   do {
      int count = countAdjacentGreater(str);
      if (count > maxCount) {
         maxCount = count;
         maxPerm = str;
      }
   } while (next_permutation(str.begin(), str.end()));
}

int main() {
   string str = "abcde";
   int maxCount = 0;
   string maxPerm;

   findMaxPermutation(str, maxCount, maxPerm);

   cout << "String with the maximum number of characters greater than its adjacent characters: " << maxPerm << endl;
   cout << "Count of adjacent characters greater in the maximum permutation: " << maxCount << endl;

   return 0;
}

输出

String with the maximum number of characters greater than its adjacent characters: abcde
Count of adjacent characters greater in the maximum permutation: 4

结论

总之，找到最大字符数大于相邻字符的字符串的排列问题是字符串操作中的一个有趣的挑战。通过分析给定的字符串并有策略地重新排列其字符，可以实现所需的排列。这个问题凸显了在使用字符串和排列时仔细检查和创造性思维的重要性。

以上是字串的排列，使得其中字元的數量大於其相鄰字元的數量的最大化的詳細內容。更多資訊請關注PHP中文網其他相關文章！