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

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 barbante str com “MUO” como os valores da string. Você foi solicitado a mostrar as permutações da string. Veja como você faria:

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.

Observação: 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:

// Programa C ++ para imprimir todos
// permutações de uma string
#incluir 
usando namespace std;
// Função para imprimir permutações de string
void findPermutations (string str, int leftIndex, int rightIndex)
{
if (leftIndex == rightIndex)
{
cout << str << endl;
}
outro
{
para (int i = leftIndex; i <= rightIndex; i ++)
{
troca (str [leftIndex], str [i]);
findPermutations (str, leftIndex + 1, rightIndex);
//backtrack
troca (str [leftIndex], str [i]);
}
}
}
// Código do driver
int main ()
{
string str1 = "MUO";
int size1 = str1.size ();
cout << "str1:" << str1 << endl;
cout << "Permutações de" << str1 << ":" << endl;
findPermutations (str1, 0, size1-1);
string str2 = "AB";
int size2 = str2.size ();
cout << "str2:" << str2 << endl;
cout << "Permutações de" << str2 << ":" << endl;
findPermutations (str2, 0, size2-1);
string str3 = "XYZ";
int size3 = str3.size ();
cout << "str3:" << str3 << endl;
cout << "Permutações de" << str3 << ":" << endl;
findPermutations (str3, 0, size3-1);
return 0;
}

Saída:

str1: MUO
Permutações de MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Permutações de AB:
AB
BA
str3: XYZ
Permutações de 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:

# Programa Python para imprimir todos
# permutações de uma string
def convertToString (List):
return '' .join (lista)
# Função para imprimir permutações de string
def findPermutations (s, leftIndex, rightIndex):
if leftIndex == rightIndex:
imprimir (convertToString (s))
outro:
para i no intervalo (leftIndex, rightIndex + 1):
s [leftIndex], s [i] = s [i], s [leftIndex]
findPermutations (s, leftIndex + 1, rightIndex)
# retroceder
s [leftIndex], s [i] = s [i], s [leftIndex]
# Código do Driver
str1 = "MUO"
tamanho1 = len (str1)
s1 = lista (str1)
imprimir ("str1:", str1)
print ("Permutações de", str1, ":")
findPermutations (s1, 0, size1-1)
str2 = "AB"
tamanho2 = len (str2)
s2 = lista (str2)
imprimir ("str2:", str2)
print ("Permutações de", str2, ":")
findPermutations (s2, 0, size2-1)
str3 = "XYZ"
tamanho3 = len (str3)
s3 = lista (str3)
imprimir ("str3:", str3)
print ("Permutações de", str3, ":")
findPermutations (s3, 0, size3-1)

Saída:

str1: MUO
Permutações de MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Permutações de AB:
AB
BA
str3: XYZ
Permutações de 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:

// Programa JavaScript para imprimir todos
// permutações de uma string
// Função para trocar caracteres da string
troca de função (str, leftIndex, i) {
deixe temp;
let tempArray = str.split ("");
temp = tempArray [leftIndex];
tempArray [leftIndex] = tempArray [i];
tempArray [i] = temp;
return (tempArray) .join ("");
}
// Função para imprimir permutações de string
function findPermutations (str, leftIndex, rightIndex) {
if (leftIndex == rightIndex) {
document.write (str + "
");
} outro {
para (deixe i = leftIndex; i <= rightIndex; i ++) {
str = troca (str, leftIndex, i);
findPermutations (str, leftIndex + 1, rightIndex);
//backtrack
str = troca (str, leftIndex, i) ;;
}
}
}
// Código do driver
var str1 = "MUO";
var size1 = str1.length;
document.write ("str1:" + str1 + "
");
document.write ("Permutações de" + str1 + ":" + "
");
findPermutations (str1, 0, size1-1);
var str2 = "AB";
var size2 = str2.length;
document.write ("str2:" + str2 + "
");
document.write ("Permutações de" + str2 + ":" + "
");
findPermutations (str2, 0, size2-1);
var str3 = "XYZ";
var size3 = str3.length;
document.write ("str3:" + str3 + "
");
document.write ("Permutações de" + str3 + ":" + "
");
findPermutations (str3, 0, size3-1);

Saída:

str1: MUO
Permutações de MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Permutações de AB:
AB
BA
str3: XYZ
Permutações de 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:

// programa C para imprimir todos
// permutações de uma string
#incluir 
#incluir 
// Função para trocar caracteres da string
void swap (char str [], int leftIndex, int i)
{
char temp = str [leftIndex];
str [leftIndex] = str [i];
str [i] = temp;
}
// Função para imprimir permutações de string
void findPermutations (char str [], int leftIndex, int rightIndex)
{
if (leftIndex == rightIndex)
{
printf ("% s \ ⁠n", str);
}
outro
{
para (int i = leftIndex; i <= rightIndex; i ++)
{
troca (str, leftIndex, i);
findPermutations (str, leftIndex + 1, rightIndex);
//backtrack
troca (str, leftIndex, i);
}
}
}
// Código do driver
int main ()
{
char str1 [] = "MUO";
int size1 = strlen (str1);
printf ("str1:% s \ ⁠n", str1);
printf ("Permutações de% s: \ ⁠n", str1);
findPermutations (str1, 0, size1-1);
char str2 [] = "AB";
tamanho2 interno = strlen (str2);
printf ("str2:% s \ ⁠n", str2);
printf ("Permutações de% s: \ ⁠n", str2);
findPermutations (str2, 0, size2-1);
char str3 [] = "XYZ";
int tamanho3 = strlen (str3);
printf ("str3:% s \ ⁠n", str3);
printf ("Permutações de% s: \ ⁠n", str3);
findPermutations (str3, 0, size3-1);
return 0;
}

Saída:

str1: MUO
Permutações de MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Permutações de AB:
AB
BA
str3: XYZ
Permutações de 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.

Yuvraj Chandra (58 artigos publicados)

Yuvraj é estudante de graduação em Ciência da Computação na Universidade de Delhi, Índia. Ele é apaixonado por Full Stack Web Development. Quando não está escrevendo, ele está explorando a profundidade de diferentes tecnologias.

Mais de Yuvraj Chandra