Программа перестановки символов строки с рекурсией

Программирование с использованием рекурсии — это мощный инструмент, который позволяет решать разнообразные задачи, включая манипуляции с данными и строками. Одной из таких задач является генерация всех перестановок символов в заданной строке. Понимание и реализация этого процесса может быть важным навыком для разработчиков и программистов. В данной статье мы погрузимся в мир рекурсии и программирования, чтобы изучить, как можно создать программу перестановки символов в строке с использованием рекурсии.

Теория

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

Определите базовый случай. Если строка состоит из одного символа (длина строки равна 1), то это единственная перестановка, и она не требует дополнительных действий. Верните эту строку как результат.
Определите случай рекурсии. Для строки длиной более 1 символа:
Выберите один символ из строки (например, первый символ).
Создайте новую строку, исключив выбранный символ из исходной строки.
Рекурсивно вызовите функцию для новой строки.
Для каждой возвращенной перестановки добавьте выбранный символ в разные позиции (перед и за каждым символом) и сохраните результат.
Соберите все перестановки из случаев рекурсии и верните их в виде массива или другой структуры данных.

Этот алгоритм рекурсивно разбивает задачу на более мелкие подзадачи, где каждая подзадача сводится к перестановке более короткой строки. По мере завершения рекурсии все перестановки объединяются в итоговый результат.

C++

Программа на C++, которая использует рекурсию для вывода всех перестановок символов в заданной строке:

#include <iostream>
#include <string>

void generatePermutations(std::string str, int left, int right) {
    if (left == right) {
        std::cout << str << std::endl;  // Вывод перестановки
    } else {
        for (int i = left; i <= right; i++) {
            std::swap(str[left], str[i]);  // Меняем символы местами
            generatePermutations(str, left + 1, right);  // Рекурсивно генерируем перестановки
            std::swap(str[left], str[i]);  // Возвращаем символы на место
        }
    }
}

int main() {
    std::string input;
    std::cout << "Введите строку: ";
    std::cin >> input;

    int n = input.size();
    generatePermutations(input, 0, n - 1);

    return 0;
}

Эта программа сначала запрашивает у пользователя строку, затем вызывает функцию generatePermutations, которая рекурсивно генерирует все перестановки символов в строке. Результаты выводятся на экран.

C#

using System;

class Program
{
    static void GeneratePermutations(string str, int left, int right)
    {
        if (left == right)
        {
            Console.WriteLine(str); // Вывод перестановки
        }
        else
        {
            for (int i = left; i <= right; i++)
            {
                str = SwapCharacters(str, left, i); // Меняем символы местами
                GeneratePermutations(str, left + 1, right); // Рекурсивно генерируем перестановки
                str = SwapCharacters(str, left, i); // Возвращаем символы на место
            }
        }
    }

    static string SwapCharacters(string str, int i, int j)
    {
        char[] chars = str.ToCharArray();
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new string(chars);
    }

    static void Main()
    {
        Console.Write("Введите строку: ");
        string input = Console.ReadLine();

        GeneratePermutations(input, 0, input.Length - 1);
    }
}

Python

def generate_permutations(str, left, right):
    if left == right:
        print(''.join(str))  # Вывод перестановки
    else:
        for i in range(left, right + 1):
            str[left], str[i] = str[i], str[left]  # Меняем символы местами
            generate_permutations(str, left + 1, right)  # Рекурсивно генерируем перестановки
            str[left], str[i] = str[i], str[left]  # Возвращаем символы на место

input_str = input("Введите строку: ")
str_list = list(input_str)
generate_permutations(str_list, 0, len(str_list) - 1)

Java

import java.util.Scanner;

public class Permutations {
    public static void generatePermutations(char[] str, int left, int right) {
        if (left == right) {
            System.out.println(new String(str)); // Вывод перестановки
        } else {
            for (int i = left; i <= right; i++) {
                swap(str, left, i); // Меняем символы местами
                generatePermutations(str, left + 1, right); // Рекурсивно генерируем перестановки
                swap(str, left, i); // Возвращаем символы на место
            }
        }
    }

    public static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Введите строку: ");
        String input = scanner.nextLine();
        char[] strArray = input.toCharArray();
        generatePermutations(strArray, 0, strArray.length - 1);
    }
}

Pascal

program Permutations;

procedure Swap(var a, b: Char);
var
  temp: Char;
begin
  temp := a;
  a := b;
  b := temp;
end;

procedure GeneratePermutations(var str: string; left, right: Integer);
begin
  if left = right then
    Writeln(str)  // Вывод перестановки
  else
  begin
    for i := left to right do
    begin
      Swap(str[left], str[i]);  // Меняем символы местами
      GeneratePermutations(str, left + 1, right);  // Рекурсивно генерируем перестановки
      Swap(str[left], str[i]);  // Возвращаем символы на место
    end;
  end;
end;

var
  input: string;
begin
  Write('Введите строку: ');
  Readln(input);

  GeneratePermutations(input, 1, Length(input));
end.

JavaScript

function generatePermutations(str, left, right) {
    if (left === right) {
        console.log(str);  // Вывод перестановки
    } else {
        for (let i = left; i <= right; i++) {
            str = swapCharacters(str, left, i);  // Меняем символы местами
            generatePermutations(str, left + 1, right);  // Рекурсивно генерируем перестановки
            str = swapCharacters(str, left, i);  // Возвращаем символы на место
        }
    }
}

function swapCharacters(str, i, j) {
    const charArray = str.split('');
    [charArray[i], charArray[j]] = [charArray[j], charArray[i]];
    return charArray.join('');
}

const inputStr = prompt("Введите строку:");
generatePermutations(inputStr, 0, inputStr.length - 1);

PHP

<?php

function generatePermutations($str, $left, $right) {
    if ($left === $right) {
        echo "$str\n";  // Вывод перестановки
    } else {
        for ($i = $left; $i <= $right; $i++) {
            $str = swapCharacters($str, $left, $i);  // Меняем символы местами
            generatePermutations($str, $left + 1, $right);  // Рекурсивно генерируем перестановки
            $str = swapCharacters($str, $left, $i);  // Возвращаем символы на место
        }
    }
}

function swapCharacters($str, $i, $j) {
    $charArray = str_split($str);
    list($charArray[$i], $charArray[$j]) = array($charArray[$j], $charArray[$i]);
    return implode('', $charArray);
}

$inputStr = readline("Введите строку: ");
generatePermutations($inputStr, 0, strlen($inputStr) - 1);

?>