Comment imprimer toutes les permutations d’une chaîne donnée en C, C++, JavaScript et Python

Hibou Gourou

Une permutation est un arrangement d'objets dans un ordre spécifique. Vous pouvez permuter une chaîne de longueur n en n ! façons.

Dans cet article, vous apprendrez à trouver toutes les permutations d'une chaîne donnée à l'aide de C++, Python, JavaScript et C.

Comment fonctionnent les permutations ?

Supposons que vous ayez une chaîne str avec « MUO » comme valeurs de chaîne. On vous a demandé d'afficher les permutations de la chaîne. Voici comment vous vous y prendriez :

Exemple 1 : Soit str = "MUO"

Les permutations de « MUO » sont :

  • "MUO"
  • "MOU"
  • « UMO »
  • « UOM »
  • "OUM"
  • « OMOU »

Notez l'ordre des valeurs. Voici un autre exemple :

Exemple 2 : Soit str = "AB"

Toutes les permutations de « AB » sont :

  • "UN B"
  • "BA"

Vous pouvez également imprimer des permutations en double s'il y a des caractères répétés dans la chaîne donnée. (ABBA, par exemple)

Maintenant que vous comprenez comment fonctionnent les permutations, voyons comment vous pouvez les trouver en utilisant votre langage de programmation préféré.

Remarque : Nous avons conçu les exemples de code suivants pour générer des permutations pour trois chaînes : MUO, AB et XYZ. Si vous souhaitez utiliser l'un de ces codes, copiez-le et modifiez ces chaînes pour les adapter à votre projet.

En relation: Comment convertir les caractères d'une chaîne dans le cas opposé avec la programmation

Programme C++ pour imprimer toutes les permutations d'une chaîne

Ci-dessous se trouve le programme C++ pour imprimer toutes les permutations d'une chaîne :

 // C++ program to print all
 // permutations of a string
 #include <bits/stdc++.h>
 using namespace std;

 // Function to print permutations of string
 void findPermutations(string str, int leftIndex, int rightIndex)
 {
 if (leftIndex == rightIndex)
 {
 cout << str << endl;
 }
 else
 {
 for (int i = leftIndex; i <= rightIndex; i++)
 {
 swap(str[leftIndex], str[i]);
 findPermutations(str, leftIndex+1, rightIndex);
 //backtrack
 swap(str[leftIndex], str[i]);
 }
 }
 }
 // Driver Code
 int main()
 {
 string str1 = "MUO";
 int size1 = str1.size();
 cout << "str1: " << str1 << endl;
 cout << "Permutations of " << str1 << ":" << endl;
 findPermutations(str1, 0, size1-1);
 string str2 = "AB";
 int size2 = str2.size();
 cout << "str2: " << str2 << endl;
 cout << "Permutations of " << str2 << ":" << endl;
 findPermutations(str2, 0, size2-1);
 string str3 = "XYZ";
 int size3 = str3.size();
 cout << "str3: " << str3 << endl;
 cout << "Permutations of " << str3 << ":" << endl;
 findPermutations(str3, 0, size3-1);
 return 0;
 }

Sortie :

 str1: MUO
 Permutations of MUO:
 MUO
 MOU
 UMO
 UOM
 OUM
 OMU
 str2: AB
 Permutations of AB:
 AB
 BA
 str3: XYZ
 Permutations of XYZ:
 XYZ
 XZY
 YXZ
 YZX
 ZYX
 ZXY

Connexe: Comment vérifier si une chaîne est symétrique avec la programmation

Programme Python pour imprimer toutes les permutations d'une chaîne

Ensuite, est le code Python pour imprimer toutes les permutations d'une chaîne :

 # Python program to print all
 # permutations of a string
 def convertToString(List):
 return ''.join(List)
 # Function to print permutations of string
 def findPermutations(s, leftIndex, rightIndex):
 if leftIndex == rightIndex:
 print(convertToString(s))
 else:
 for i in range(leftIndex, rightIndex+1):
 s[leftIndex], s[i] = s[i], s[leftIndex]
 findPermutations(s, leftIndex+1, rightIndex)
 # backtrack
 s[leftIndex], s[i] = s[i], s[leftIndex]
 # Driver Code
 str1 = "MUO"
 size1 = len(str1)
 s1 = list(str1)
 print("str1:", str1)
 print("Permutations of", str1,":")
 findPermutations(s1, 0, size1-1)
 str2 = "AB"
 size2 = len(str2)
 s2 = list(str2)
 print("str2:", str2)
 print("Permutations of", str2,":")
 findPermutations(s2, 0, size2-1)
 str3 = "XYZ"
 size3 = len(str3)
 s3 = list(str3)
 print("str3:", str3)
 print("Permutations of", str3,":")
 findPermutations(s3, 0, size3-1)

Sortie :

 str1: MUO
 Permutations of MUO:
 MUO
 MOU
 UMO
 UOM
 OUM
 OMU
 str2: AB
 Permutations of AB:
 AB
 BA
 str3: XYZ
 Permutations of XYZ:
 XYZ
 XZY
 YXZ
 YZX
 ZYX
 ZXY

En relation: Comment vérifier si deux chaînes sont des anagrammes l'une de l'autre

Programme JavaScript pour imprimer toutes les permutations d'une chaîne

Voici comment imprimer les permutations en JavaScript :

 // JavaScript program to print all
 // permutations of a string
 // Function to swap characters of the string
 function swap(str, leftIndex, i) {
 let temp;
 let tempArray = str.split("");
 temp = tempArray[leftIndex] ;
 tempArray[leftIndex] = tempArray[i];
 tempArray[i] = temp;
 return (tempArray).join("");
 }
 // Function to print permutations of string
 function findPermutations(str, leftIndex, rightIndex) {
 if (leftIndex == rightIndex) {
 document.write(str + "<br>");
 } else {
 for (let i = leftIndex; i <= rightIndex; i++) {
 str = swap(str, leftIndex, i);
 findPermutations(str, leftIndex+1, rightIndex);
 //backtrack
 str = swap(str, leftIndex, i);;
 }
 }
 }
 // Driver Code
 var str1 = "MUO";
 var size1 = str1.length;
 document.write("str1: " + str1 + "<br>");
 document.write("Permutations of " + str1 + ":" + "<br>");
 findPermutations(str1, 0, size1-1);
 var str2 = "AB";
 var size2 = str2.length;
 document.write("str2: " + str2 + "<br>");
 document.write("Permutations of " + str2 + ":" + "<br>");
 findPermutations(str2, 0, size2-1);
 var str3 = "XYZ";
 var size3 = str3.length;
 document.write("str3: " + str3 + "<br>");
 document.write("Permutations of " + str3 + ":" + "<br>");
 findPermutations(str3, 0, size3-1);

Sortie :

 str1: MUO
 Permutations of MUO:
 MUO
 MOU
 UMO
 UOM
 OUM
 OMU
 str2: AB
 Permutations of AB:
 AB
 BA
 str3: XYZ
 Permutations of XYZ:
 XYZ
 XZY
 YXZ
 YZX
 ZYX
 ZXY

Connexes : Comment relever le défi FizzBuzz dans 5 langages de programmation

Programme C pour imprimer toutes les permutations d'une chaîne

Vous trouverez ci-dessous un programme C qui imprime toutes les permutations d'une chaîne :

 // C program to print all
 // permutations of a string
 #include <stdio.h>
 #include <string.h>
 // Function to swap characters of the string
 void swap(char str[], int leftIndex, int i)
 {
 char temp = str[leftIndex];
 str[leftIndex] = str[i];
 str[i] = temp;
 }
 // Function to print permutations of string
 void findPermutations(char str[], int leftIndex, int rightIndex)
 {
 if (leftIndex == rightIndex)
 {
 printf("%s ⁠n", str);
 }
 else
 {
 for (int i = leftIndex; i <= rightIndex; i++)
 {
 swap(str, leftIndex, i);
 findPermutations(str, leftIndex+1, rightIndex);
 //backtrack
 swap(str, leftIndex, i);
 }
 }
 }
 // Driver Code
 int main()
 {
 char str1[] = "MUO";
 int size1 = strlen(str1);
 printf("str1: %s ⁠n", str1);
 printf("Permutations of %s: ⁠n", str1);
 findPermutations(str1, 0, size1-1);
 char str2[] = "AB";
 int size2 = strlen(str2);
 printf("str2: %s ⁠n", str2);
 printf("Permutations of %s: ⁠n", str2);
 findPermutations(str2, 0, size2-1);
 char str3[] = "XYZ";
 int size3 = strlen(str3);
 printf("str3: %s ⁠n", str3);
 printf("Permutations of %s: ⁠n", str3);
 findPermutations(str3, 0, size3-1);
 return 0;
 }

Sortie :

 str1: MUO
 Permutations of MUO:
 MUO
 MOU
 UMO
 UOM
 OUM
 OMU
 str2: AB
 Permutations of AB:
 AB
 BA
 str3: XYZ
 Permutations of XYZ:
 XYZ
 XZY
 YXZ
 YZX
 ZYX
 ZXY

L'impression des permutations est facile

Dans cet article, vous avez appris à imprimer toutes les permutations d'une chaîne dans plusieurs langages de programmation. Bien que ces exemples de programmes ne soient pas le seul moyen de gérer les permutations, ils constituent un bon début pour ceux qui débutent dans leur utilisation dans leur code.