En permutation är ett arrangemang av objekt i en specifik ordning. Du kan permutera en sträng med längden n i n! sätt.
I den här artikeln kommer du att lära dig hur du hittar alla permutationer för en given sträng med C++, Python, JavaScript och C.
Hur fungerar permutationer?
Låt oss säga att du har snöre str med “MUO” som strängvärden. Du har blivit ombedd att visa strängens permutationer. Så här skulle du gå tillväga:
Exempel 1: Låt str = “MUO”
Permutationerna för “MUO” är:
“MUO” “MOU” “UMO” “UOM” “OUM” “OMU”
Notera ordningen på värdena. Här är ett annat exempel:
Exempel 2: Låt str = “AB”
Alla permutationer av “AB” är:
Du kan också skriva ut dubbletter av permutationer om det finns upprepade tecken i den givna strängen. (ABBA, till exempel)
Nu när du förstår hur permutationer fungerar, låt oss ta en titt på hur du kan hitta dem med ditt föredragna programmeringsspråk.
Notera: Vi har designat följande kodexempel för att mata ut permutationer för tre strängar: MUO, AB och XYZ. Om du vill använda någon av denna kod, kopiera den och ändra dessa strängar så att de passar ditt projekt.
C++-program för att skriva ut alla permutationer av en sträng
Nedan är C++-programmet för att skriva ut alla permutationer av en sträng:
// 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;
}
Produktion:
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
Python-program för att skriva ut alla permutationer av en sträng
Därefter är Python-koden för att skriva ut alla permutationer av en sträng:
# 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)
Produktion:
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
JavaScript-program för att skriva ut alla permutationer av en sträng
Så här skriver du ut permutationer i 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);
Produktion:
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
C Program för att skriva ut alla permutationer av en sträng
Nedan finns ett C-program som skriver ut alla permutationer av en sträng:
// 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;
}
Produktion:
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
Det är enkelt att skriva ut permutationer
I den här artikeln har du lärt dig hur du skriver ut alla permutationer av en sträng på flera programmeringsspråk. Även om dessa exempelprogram inte är det enda sättet att hantera permutationer, är de en bra början för dem som är nya med att använda dem i sin kod.
Om författaren
Yuvraj Chandra (80 artiklar publicerade)
Yuvraj är en datavetenskapsstudent vid University of Delhi, Indien. Han brinner för Full Stack Web Development. När han inte skriver undersöker han djupet i olika teknologier.
Mer från Yuvraj Chandra
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
