Classement lexicographique des chaînes binaires

Dans cet article, nous explorerons un problème intéressant impliquant les chaînes binaires et l'ordre lexicographique. Notre tâche est de trouver le classement lexicographique d'une chaîne binaire donnée. Nous démontrerons notre solution en utilisant C++, un langage de programmation populaire connu pour son efficacité et sa flexibilité.

Comprendre l'ordre des dictionnaires

L'ordre du dictionnaire (également appelé ordre alphabétique ou ordre du dictionnaire) est la disposition des mots par ordre alphabétique en fonction de leurs lettres constitutives.

Énoncé du problème

Étant donné une chaîne binaire, nous devons déterminer son classement lexicographique parmi toutes les permutations. Le rang lexicographique d'une chaîne est sa position dans l'ensemble de toutes les permutations lorsqu'elles sont répertoriées lexicographiquement.

Méthode de solution

Notre approche comprend les étapes clés suivantes−

• Initialize Count − Initialise un compteur pour stocker le nombre de « 1 » dans la chaîne binaire.

• Calcul du classement − Parcourt itérativement la chaîne binaire de gauche à droite. Si le caractère actuel est « 1 », calculez son rang à l'aide d'une formule combinée et décrémentez le compteur pour chaque « 1 » suivant.

• Return Result− Le résultat sera l'ordre lexicographique de la chaîne binaire.

Implémentation C++

Exemple

Le code C++ ci-dessous présente notre solution−

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

// Function to calculate factorial
int fact(int n) {
   int res = 1;
   for (int i = 1; i <= n; i++)
      res *= i;
   return res;
}

// Function to find lexicographic rank of a binary string
int lexRank(string str) {
   int rank = 1;
   int onesCount = count(str.begin(), str.end(), '1');
   
   for (char c : str) {
      if (c == '1') {
         onesCount--;
         rank += fact(onesCount);
      }
   }
   
   return rank;
}

int main() {
   string str = "110";
   
   int result = lexRank(str);
   cout << "Lexicographic rank of the binary string: " << result << endl;
   
   return 0;
}

Sortie

Lexicographic rank of the binary string: 3

La traduction chinoise de

Explication

est :

Explication

Considérez la chaîne binaire −

str = "110"

Les permutations et combinaisons de cette chaîne binaire sont : "011", "101", "110". Par ordre lexicographique, ces permutations sont : "011", "101", "110".

La chaîne binaire "110" a un rang de 3 et c'est la sortie de notre programme.

Conclusion

Le problème de trouver le classement lexicographique d'une chaîne binaire est un problème très intéressant qui repose sur notre compréhension des chaînes binaires, des permutations et de l'ordre lexicographique. Cette solution implémentée en C++ montre comment nous pouvons utiliser des constructions de programmation de base pour résoudre efficacement ce problème.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!