Ordnen Sie Zeichenfolgen so an, dass die Anzahl der darin enthaltenen Zeichen größer ist als die Anzahl der angrenzenden Zeichen.

Die Manipulation von Zeichenfolgen ist in einer Vielzahl von Problemlösungsszenarien von entscheidender Bedeutung. Durch die Permutation einer bestimmten Zeichenfolge wird die Anzahl der Zeichen optimiert, die größer ist als die Anzahl der angrenzenden Zeichen. Dies ist ein interessantes Rätsel, bei dem die Zeichen einer Zeichenfolge neu angeordnet werden müssen, um so viele Paare benachbarter Zeichen wie möglich zu erzeugen Die Zeichen links sind kleiner als die Zeichen rechts. p>

Methode

Es gibt mehrere Möglichkeiten, Permutationen von Zeichenfolgen zu lösen, bei denen die maximale Anzahl von Zeichen größer ist als die Anzahl der direkt angrenzenden Zeichen.

Methode 1 − Zurückverfolgen und Beschneiden −

Methode 2 – Dynamische Programmierung –

Methode 3 – Heap-Algorithmus –

Methode 4 – Wörterbuchreihenfolge mit Beschneiden –

Methode 1: Zurückverfolgen und Beschneiden

• Generieren Sie alle Permutationen der Zeichenfolge mithilfe eines Backtracking-Algorithmus.

• Überprüfen Sie bei jedem Schritt, ob die aktuelle Anordnung mehr Zeichen als ihre Nachbarn hat, die größer sind als das bisher gefundene Maximum.

• Wenn nicht, beschneiden Sie den Zweig frühzeitig und gehen Sie zurück, um unnötige Berechnungen zu vermeiden.

Grammatik

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

• Speichern Sie die maximale Anzahl von Zeichen, die größer sind als benachbarte Zeichen.

result = [None] * n 

• Endgültige Vereinbarung speichern

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

• Zählen Sie die Anzahl der Zeichen, die größer als die angrenzenden Zeichen sind

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  

• Ergebnisse aktualisieren

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

• Wählen Sie das nächste Zeichen

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

• Zurück zum nächsten Ort

backtrack(curr_permutation, used_chars)

• Auswahl rückgängig machen

used_chars[i] = false
curr_permutation.pop()

• Starten Sie den Backtracking-Prozess

used_chars = [false] * n 

• Verfolgte verwendete Zeichen

curr_permutation = []
backtrack(curr_permutation, used_chars)

return result.

Algorithmus

Schritt 1 – Starten Sie max_permutation mit einer leeren Zeichenfolge.

• Hilfsfunktions-Traceback (aktuelle_Permutation, verbleibende_Zeichen) sollte definiert werden.

Schritt 2 – Wenn die Zeichenfolge „remaining_characters“ leer ist –

• Wenn die Länge der aktuellen Permutation länger ist als die Länge der größten Permutation, setzen Sie max_permutation auf current_permutation.

• Rückkehr.

Schritt 3 – Durchlaufen Sie in einer Iteration jedes der verbleibenden Zeichen c -

• Fügen Sie c zur aktuellen_Permutation hinzu, um eine neue_Permutation zu erstellen.

• Wenn die Länge von new_permutation größer als 1 ist und das letzte Zeichen nicht länger als die vorhergehenden Zeichen ist, überspringen Sie diese Iteration.

• Nehmen Sie c aus den verbleibenden_Zeichen und generieren Sie neue neue_verbleibende Zeichen.

• Iteratives Aufruf-Traceback (new_permutation, new_remaining).

Schritt 4 – Rufen Sie die Traceback-Funktion auf und verwenden Sie dabei den Eingabetext als verbleibende_Zeichen und die leere Zeichenfolge als aktuelle_Permutation.

Schritt 5 – Geben Sie die Ausgabe max_permutation an.

Beispiel 1

Dieses Programm sortiert zunächst die Eingabezeichenfolge „abcd“ in aufsteigender Reihenfolge. Jede mögliche Permutation wird dann mithilfe einer Backtracking-Funktion generiert, die nur größere Zeichen als die vorherige berücksichtigt und so wiederholte Permutationen vermeidet, die die Kriterien nicht erfüllen. Darüber hinaus wertet die Funktion isValidPermutation jedes Zeichen anhand seines vorhergehenden Zeichens aus und gibt für jedes Zeichen, das gleich oder kleiner als dieses ist, „false“ zurück.

Das Ergebnis ist, dass dieser gezielte Prozess alle gültigen Permutationen erstellt, bei denen die maximale Anzahl jedes Zeichens höher ist als die seiner Nachbarzeichen. Es steht uns frei, die angegebenen Eingabezeichenfolgen, den Code und die Logik weiter an individuelle Anforderungen anzupassen.

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

Ausgabe

abcd

Methode 2: Dynamische Programmierung

• Verwenden Sie dynamische Programmierung, um nach und nach Permutationen von Zeichenfolgen zu generieren.

• Beginnen Sie mit einem leeren Präfix, berücksichtigen Sie alle möglichen Positionen und fügen Sie iterativ Zeichen hinzu.

• Behalten Sie die Anzahl der Zeichen im aktuellen Präfix bei, die größer sind als die angrenzenden Zeichen.

• Beschneiden Sie Zweige, deren Anzahl unter den bisher gefundenen Höchstwert gefallen ist.

Grammatik

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

• Dynamische Programmierschleife

for i in range (1, n):

• Überprüfen Sie, ob das aktuelle Zeichen größer als das angrenzende Zeichen ist

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

• Wenn ja, erhöhen Sie die Anzahl um 1

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

• Wenn nicht, ist die Zählung gleich

dp[i] = dp[i-1]

• Finden Sie die maximale Anzahl im dp-Array

max_count = max(dp)

return max_count

Algorithmus

Schritt 1 – Erstellen Sie eine Funktion namens maxPerm(str), die eine Zeichenfolge als Eingabe akzeptiert und die Permutation der längsten Zeichenfolge zurückgibt, die die angegebenen Kriterien erfüllt.

Schritt 2 – Initialisieren Sie zunächst ein Array (genannt dp) der Länge n, wobei n gleich der Länge der Eingabezeichenfolge str ist. Die maximale Permutationszeichenfolge, die an Position i endet, wird in jedem Element dp[i] gespeichert.

Schritt 3 – Initialisieren Sie dp[0] mit dem ersten Zeichen der Zeichenfolge str.

Schritt 4 – Durchlaufen Sie die Zeichen von str von Index 1 bis n-1 -

• 初始化一个空字符串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

结论

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

Das obige ist der detaillierte Inhalt vonOrdnen Sie Zeichenfolgen so an, dass die Anzahl der darin enthaltenen Zeichen größer ist als die Anzahl der angrenzenden Zeichen.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!