Как да отпечатате всички пермутации на даден низ в C, C ++, JavaScript и Python

Пермутацията е подреждане на обекти в определен ред. Можете да пермутирате низ с дължина n в n! начини.

В тази статия ще научите как да намерите всички пермутации на даден низ, използвайки C ++, Python, JavaScript и C.

Как работят пермутациите?

Да предположим, че имате низ ул с „MUO“ като низови стойности. От вас се иска да покажете пермутациите на низа. Ето как бихте постъпили по въпроса:

Пример 1: Нека str = "MUO"

Пермутациите на „MUO“ са:

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

Обърнете внимание на реда на стойностите. Ето още един пример:

Пример 2: Нека str = "AB"

Всички пермутации на „AB“ са:

• „AB“
• „БА“

Можете също да отпечатате дублирани пермутации, ако в дадения низ има повтарящи се знаци. (ABBA, например)

Сега, когато разбирате как работят пермутациите, нека да разгледаме как можете да ги намерите, като използвате предпочитания от вас език за програмиране.

Забележка: Ние проектирахме следните примери за код за извеждане на пермутации за три низа: MUO, AB и XYZ. Ако искате да използвате някой от този код, копирайте го и променете тези низове, за да отговарят на вашия проект.

Свързани: Как да конвертирате символи на низ в противоположния случай с програмиране

C ++ програма за отпечатване на всички пермутации на низ

По -долу е програмата C ++ за отпечатване на всички пермутации на низ:

// C ++ програма за отпечатване на всички
// пермутации на низ
#включва 
използване на пространство от имена std;
// Функция за отпечатване на пермутации на низ
void findPermutations (string str, int leftIndex, int rightIndex)
{
ако (leftIndex == rightIndex)
{
cout << str << endl;
}
иначе
{
for (int i = leftIndex; i <= rightIndex; i ++)
{
суап (str [leftIndex], str [i]);
findPermutations (str, leftIndex+1, rightIndex);
//backtrack
суап (str [leftIndex], str [i]);
}
}
}
// Код на водача
int main ()
{
низ str1 = "MUO";
int size1 = str1.size ();
cout << "str1:" << str1 << endl;
cout << "Пермутации на" << str1 << ":" << endl;
findPermutations (str1, 0, size1-1);
низ str2 = "AB";
int size2 = str2.size ();
cout << "str2:" << str2 << endl;
cout << "Пермутации на" << str2 << ":" << endl;
findPermutations (str2, 0, size2-1);
низ str3 = "XYZ";
int size3 = str3.size ();
cout << "str3:" << str3 << endl;
cout << "Пермутации на" << str3 << ":" << endl;
findPermutations (str3, 0, size3-1);
връщане 0;
}

Изход:

str1: MUO
Пермутации на MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Пермутации на AB:
AB
BA
str3: XYZ
Пермутации на XYZ:
XYZ
XZY
YXZ
YZX
ZYX
ZXY

Свързани: Как да проверите дали низ е симетричен с програмиране

Програма Python за отпечатване на всички пермутации на низ

След това кодът на Python за отпечатване на всички пермутации на низ:

# Програма Python за отпечатване на всички
# пермутации на низ
def convertToString (Списък):
return '' .join (Списък)
# Функция за отпечатване на пермутации на низ
def findPermutations (s, leftIndex, rightIndex):
if leftIndex == rightIndex:
печат (convertToString (s))
иначе:
за i в обхват (leftIndex, rightIndex+1):
s [leftIndex], s [i] = s [i], s [leftIndex]
findPermutations (s, leftIndex+1, rightIndex)
# връщане назад
s [leftIndex], s [i] = s [i], s [leftIndex]
# Код на водача
str1 = "MUO"
size1 = len (str1)
s1 = списък (str1)
print ("str1:", str1)
print ("Пермутации на", str1, ":")
findPermutations (s1, 0, size1-1)
str2 = "AB"
size2 = len (str2)
s2 = списък (str2)
print ("str2:", str2)
print ("Пермутации на", str2, ":")
findPermutations (s2, 0, size2-1)
str3 = "XYZ"
размер3 = len (str3)
s3 = списък (str3)
print ("str3:", str3)
print ("Пермутации на", str3, ":")
findPermutations (s3, 0, size3-1)

Изход:

str1: MUO
Пермутации на MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Пермутации на AB:
AB
BA
str3: XYZ
Пермутации на XYZ:
XYZ
XZY
YXZ
YZX
ZYX
ZXY

Свързани: Как да проверите дали две струни са анаграми един на друг

JavaScript програма за отпечатване на всички пермутации на низ

Ето как отпечатвате пермутации в JavaScript:

// JavaScript програма за отпечатване на всички
// пермутации на низ
// Функция за размяна на знаци от низ
функция swap (str, leftIndex, i) {
оставете температура;
нека tempArray = str.split ("");
temp = tempArray [leftIndex];
tempArray [leftIndex] = tempArray [i];
tempArray [i] = temp;
return (tempArray) .join ("");
}
// Функция за отпечатване на пермутации на низ
функция findPermutations (str, leftIndex, rightIndex) {
if (leftIndex == rightIndex) {
document.write (str + "
");
} else {
for (нека i = leftIndex; i <= rightIndex; i ++) {
str = swap (str, leftIndex, i);
findPermutations (str, leftIndex+1, rightIndex);
//backtrack
str = swap (str, leftIndex, i) ;;
}
}
}
// Код на водача
var str1 = "MUO";
var size1 = str1.length;
document.write ("str1:" + str1 + "
");
document.write ("Пермутации на" + str1 + ":" + "
");
findPermutations (str1, 0, size1-1);
var str2 = "AB";
var size2 = str2.length;
document.write ("str2:" + str2 + "
");
document.write ("Пермутации на" + str2 + ":" + "
");
findPermutations (str2, 0, size2-1);
var str3 = "XYZ";
var size3 = str3.length;
document.write ("str3:" + str3 + "
");
document.write ("Пермутации на" + str3 + ":" + "
");
findPermutations (str3, 0, size3-1);

Изход:

str1: MUO
Пермутации на MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Пермутации на AB:
AB
BA
str3: XYZ
Пермутации на XYZ:
XYZ
XZY
YXZ
YZX
ZYX
ZXY

Свързани: Как да завършите предизвикателството на FizzBuzz на 5 езика за програмиране

C Програма за отпечатване на всички пермутации на низ

По -долу е C програма, която отпечатва всички пермутации на низ:

// C програма за отпечатване на всички
// пермутации на низ
#включва 
#включва 
// Функция за размяна на знаци от низ
void swap (char str [], int leftIndex, int i)
{
char temp = str [leftIndex];
str [leftIndex] = str [i];
str [i] = temp;
}
// Функция за отпечатване на пермутации на низ
void findPermutations (char str [], int leftIndex, int rightIndex)
{
ако (leftIndex == rightIndex)
{
printf ("%s \ ⁠n", str);
}
иначе
{
for (int i = leftIndex; i <= rightIndex; i ++)
{
суап (str, leftIndex, i);
findPermutations (str, leftIndex+1, rightIndex);
//backtrack
суап (str, leftIndex, i);
}
}
}
// Код на водача
int main ()
{
char str1 [] = "MUO";
int size1 = strlen (str1);
printf ("str1: %s \ ⁠n", str1);
printf ("Пермутации на %s: \ ⁠n", str1);
findPermutations (str1, 0, size1-1);
char str2 [] = "AB";
int size2 = strlen (str2);
printf ("str2: %s \ ⁠n", str2);
printf ("Пермутации на %s: \ ⁠n", str2);
findPermutations (str2, 0, size2-1);
char str3 [] = "XYZ";
int size3 = strlen (str3);
printf ("str3: %s \ ⁠n", str3);
printf ("Пермутации на %s: \ ⁠n", str3);
findPermutations (str3, 0, size3-1);
връщане 0;
}

Изход:

str1: MUO
Пермутации на MUO:
MUO
MOU
UMO
UOM
OUM
OMU
str2: AB
Пермутации на AB:
AB
BA
str3: XYZ
Пермутации на XYZ:
XYZ
XZY
YXZ
YZX
ZYX
ZXY

Отпечатването на пермутации е лесно

В тази статия сте научили как да отпечатвате всички пермутации на низ в няколко езика за програмиране. Въпреки че тези примерни програми не са единственият начин за справяне с пермутации, те са чудесно начало за тези, които са нови за използването им в кода си.

Юврадж Чандра (58 статии са публикувани)

Юврадж е студент по компютърни науки в Университета в Делхи, Индия. Той е страстен за Full Stack Web Development. Когато не пише, той изследва дълбочината на различните технологии.

Още от Yuvraj Chandra