Como imprimir todas as permutações de uma determinada string em C, C ++, JavaScript e Python

gurinho

Uma permutação é um arranjo de objetos em uma ordem específica. Você pode permutar uma string de comprimento n em n! maneiras.

Neste artigo, você aprenderá como encontrar todas as permutações de uma determinada string usando C ++, Python, JavaScript e C.

Como funcionam as permutações?

Digamos que você tenha string str com “MUO” como valores de string. Você foi solicitado a mostrar as permutações da string. Veja como você faria isso:

Exemplo 1 : Seja str = "MUO”

As permutações de "MUO" são:

  • “MUO”
  • "MOU"
  • “UMO”
  • “UOM”
  • “OUM”
  • “OMU”

Observe a ordem dos valores. Aqui está outro exemplo:

Exemplo 2 : Seja str = "AB”

Todas as permutações de "AB" são:

  • “AB”
  • "BA"

Você também pode imprimir permutações duplicadas se houver caracteres repetidos na string fornecida. (ABBA, por exemplo)

Agora que você entende como as permutações funcionam, vamos dar uma olhada em como você pode encontrá-las usando sua linguagem de programação preferida.

Nota : Projetamos os seguintes exemplos de código para permutações de saída para três strings: MUO, AB e XYZ. Se você quiser usar qualquer um desses códigos, copie-o e altere essas strings para que se ajustem ao seu projeto.

Relacionado: Como converter caracteres de uma string para o caso oposto com programação

Programa C ++ para imprimir todas as permutações de uma string

Abaixo está o programa C ++ para imprimir todas as permutações de uma string:

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

Produto :

 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

Relacionado: Como verificar se uma string é simétrica com a programação

Programa Python para imprimir todas as permutações de uma string

Em seguida, é o código Python para imprimir todas as permutações de uma string:

 # 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)

Produto :

 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

Relacionado: Como verificar se duas strings são anagramas uma da outra

Programa JavaScript para imprimir todas as permutações de uma string

Veja como imprimir permutações em 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);

Produto :

 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

Relacionado: Como completar o desafio FizzBuzz em 5 linguagens de programação

Programa C para imprimir todas as permutações de uma string

Abaixo está um programa C que imprime todas as permutações de uma string:

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

Produto :

 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

Imprimir permutações é fácil

Neste artigo, você aprendeu como imprimir todas as permutações de uma string em várias linguagens de programação. Embora esses programas de amostra não sejam a única maneira de lidar com permutações, eles são um ótimo começo para aqueles que são novos em usá-los em seu código.