Перестановки строки в C++, Python, JavaScript и C

Кусочки пазла на деревянной поверхности

TL;DR

Кратко: перестановки строки — все возможные упорядоченные расположения её символов. В статье показаны рекурсивные реализации для C++, Python, JavaScript и C, а также альтернативы, оценка сложности и рекомендации по применению.

Перестановка — это упорядоченное расположение элементов. Строку длины n можно переставить n! способами (n факториал). В этой статье показано, как сгенерировать и вывести все перестановки строки на четырёх популярных языках программирования.

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

Рассмотрим строку str со значениями “MUO”. Нам нужно вывести все перестановки этой строки.

Пример 1: str = “MUO”

Все перестановки “MUO”:

Пример 2: str = “AB”

Все перестановки “AB”:

Если в строке есть повторяющиеся символы (например “ABBA”), рекурсивный метод, который меняет местами символы, выведет повторяющиеся перестановки. При необходимости можно фильтровать дубликаты.

Важно: примеры кода выводят перестановки для строк MUO, AB и XYZ. При желании замените эти строки на свои.

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

Ниже — рекурсивная реализация на C++, которая меняет символы местами и использует бэктрекинг.

// C++ program to print all
// permutations of a string
#include 
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: программа для вывода всех перестановок строки

Рекурсивный подход с функцией swap, которая работает со строкой через массив символов.

// 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 + "\n");
    } 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 + "\n");
document.write("Permutations of " + str1 + ":" + "\n");
findPermutations(str1, 0, size1-1);

var str2 = "AB";
var size2 = str2.length;
document.write("str2: " + str2 + "\n");
document.write("Permutations of " + str2 + ":" + "\n");
findPermutations(str2, 0, size2-1);

var str3 = "XYZ";
var size3 = str3.length;
document.write("str3: " + str3 + "\n");
document.write("Permutations of " + str3 + ":" + "\n");
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

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

Рекурсивная реализация на С с явной функцией swap для массива символов.

// C program to print all
// permutations of a string
#include 
#include 

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

Оценка сложности и факты

Время: генерация всех перестановок требует O(n * n!) операций в худшем случае — для каждой перестановки обычно выполняется O(n) работы для вывода или копирования.
Память: рекурсивный метод использует O(n) стековой памяти (глубина рекурсии равна длине строки), а итоговый набор перестановок занимает O(n!) места, если сохранять их все.

Факт: для n ≥ 10 число перестановок (10! = 3 628 800) уже становится большим для хранения в памяти на большинстве машин.

Когда рекурсивный метод не подходит

Если строка длинная (n ≥ 10–12), количество перестановок экспоненциально растёт — хранить или перебирать их все нецелесообразно.
Если нужны уникальные перестановки при наличии повторяющихся символов, простой обмен местами выдаст дубликаты — используйте сортировку + next_permutation или структуру set для фильтрации.
Если нужно ленивое перечисление (по одному элементу) — лучше итераторы или генераторы (yield в Python, генераторы в C# и т.д.).

Альтернативные подходы

C++: std::next_permutation (нужна предварительная сортировка), генерирует перестановки в лексикографическом порядке.
Python: itertools.permutations возвращает итератор всех комбинаций длины n.
Итеративные алгоритмы получения перестановок (Heap’s algorithm) могут быть эффективнее по количеству обменов.
Генерация комбинаций в лексикографическом порядке полезна, если нужен строго упорядоченный вывод.

Мини-методология: как подойти к задаче

Оцените n и требование по уникальности.
Если n маленькое (≤8–9), рекурсивный вывод подходит.
Если символы могут повторяться, решите: фильтровать или генерировать уникальные сразу.
Выберите реализацию: рекурсивная, next_permutation, itertools или Heap.
Тестируйте на граничных случаях: пустая строка, строка длины 1, повторяющиеся символы.

Критерии приёмки

Все перестановки для тестовой строки (без дубликатов, если это требование) сгенерированы.
Порядок вывода соответствует ожидаемому (если требуется), либо явно указано, что порядок произвольный.
Алгоритм корректно обрабатывает пустую строку и строки с повторяющимися символами.
Производительность допустима для ожидаемого n.

Однострочный словарь терминов

Факториал n! — произведение всех целых чисел от 1 до n; даёт количество перестановок строки длины n.

Краткое резюме

Рекурсивный обмен символов — простой и интуитивный способ с бэктрекингом.
Для больших n используйте итераторы, std::next_permutation или специализированные алгоритмы.
Учитывайте повторяющиеся символы и оценку по времени/памяти.

Спасибо за чтение — поменяйте тестовые строки в примерах на свои, чтобы быстро адаптировать код под проект.