Как напечатать все перестановки данной строки в C, C ++, JavaScript и Python

Дядя Влад

Перестановка – это расположение объектов в определенном порядке. Вы можете переставить строку длины n в n! способами.

В этой статье вы узнаете, как найти все перестановки заданной строки с помощью C ++, Python, JavaScript и C.

Как работают перестановки?

Допустим, у вас есть строка str с «MUO» в качестве строковых значений. Вас попросили показать перестановки строки. Вот как бы вы это сделали:

Пример 1. Пусть str = "MUO"

Варианты «MUO»:

  • «МУО»
  • «МОУ»
  • «УМО»
  • «УОМ»
  • «ОУМ»
  • «ОМУ»

Обратите внимание на порядок значений. Вот еще один пример:

Пример 2. Пусть str = "AB"

Все варианты «AB»:

  • «AB»
  • «БА»

Вы также можете распечатать повторяющиеся перестановки, если в данной строке есть повторяющиеся символы. (Например, ABBA)

Теперь, когда вы понимаете, как работают перестановки, давайте посмотрим, как их найти, используя предпочитаемый вами язык программирования.

Примечание . Мы разработали следующие примеры кода для вывода перестановок для трех строк: MUO, AB и XYZ. Если вы хотите использовать какой-либо из этого кода, скопируйте его и измените эти строки, чтобы они соответствовали вашему проекту.

Связанный: Как преобразовать символы строки в противоположный случай с помощью программирования

Программа C ++ для печати всех перестановок строки

Ниже приведена программа на C ++ для печати всех перестановок строки:

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

Выход :

 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 для печати всех перестановок строки

Далее идет код Python для печати всех перестановок строки:

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

Выход :

 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 для печати всех перестановок строки

Вот как вы печатаете перестановки в 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);

Выход :

 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

Связанный: Как пройти испытание FizzBuzz на 5 языках программирования

Программа на C для печати всех перестановок строки

Ниже приведена программа на языке C, которая печатает все перестановки строки:

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

Выход :

 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

Печать перестановок – это просто

В этой статье вы узнали, как распечатать все перестановки строки на нескольких языках программирования. Хотя эти примеры программ – не единственный способ обработки перестановок, они являются отличным началом для тех, кто плохо знаком с их использованием в своем коде.