Рубрики

Напишите программу для печати всех перестановок данной строки

Перестановка, также называемая «номером компоновки» или «порядком», представляет собой перестановку элементов упорядоченного списка S в соответствие «один к одному» с самим S. Строка длиной n имеет n! перестановка.
Источник: Mathword ( http://mathworld.wolfram.com/Permutation.html )

Ниже приведены перестановки строки ABC.
ABC ACB BAC BCA CBA CAB

Вот решение, которое используется в качестве основы для отслеживания.

C ++

// C ++ программа для печати всего
// разрешены перестановки с дубликатами
#include <bits/stdc++.h>

using namespace std;

  

  
// Функция для печати перестановок строки
// Эта функция принимает три параметра:
// 1. Строка
// 2. Начальный индекс строки
// 3. Конечный индекс строки.

void permute(string a, int l, int r) 

    // Базовый вариант

    if (l == r) 

        cout<<a<<endl; 

    else

    

        // Перестановки сделаны

        for (int i = l; i <= r; i++) 

        

  

            // Обмен сделан

            swap(a[l], a[i]); 

  

            // рекурсия называется

            permute(a, l+1, r); 

  

            // отступаться

            swap(a[l], a[i]); 

        

    

  
// Код драйвера

int main() 

    string str = "ABC"

    int n = str.size(); 

    permute(str, 0, n-1); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для печати всех перестановок с разрешенными дубликатами
#include <stdio.h>
#include <string.h>

  
/ * Функция для обмена значениями в двух указателях * /

void swap(char *x, char *y)

{

    char temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

  
/ * Функция для печати перестановок строки

   Эта функция принимает три параметра:

   1. Строка

   2. Начальный индекс строки

   3. Конечный индекс строки. * /

void permute(char *a, int l, int r)

{

   int i;

   if (l == r)

     printf("%s\n", a);

   else

   {

       for (i = l; i <= r; i++)

       {

          swap((a+l), (a+i));

          permute(a, l+1, r);

          swap((a+l), (a+i)); // отступаться

       }

   }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    char str[] = "ABC";

    int n = strlen(str);

    permute(str, 0, n-1);

    return 0;

}

Джава

// Java-программа для печати всех перестановок
// заданная строка.

public class Permutation

{

    public static void main(String[] args)

    {

        String str = "ABC";

        int n = str.length();

        Permutation permutation = new Permutation();

        permutation.permute(str, 0, n-1);

    }

  

    /**

     * permutation function

     * @param str string to calculate permutation for

     * @param l starting index

     * @param r end index

     */

    private void permute(String str, int l, int r)

    {

        if (l == r)

            System.out.println(str);

        else

        {

            for (int i = l; i <= r; i++)

            {

                str = swap(str,l,i);

                permute(str, l+1, r);

                str = swap(str,l,i);

            }

        }

    }

  

    / **

     * Обмен персонажей на позиции

     * @param строковое значение

     * @param I позиция 1

     * @парам j позиция 2

     * @return поменялась строка

     * /

    public String swap(String a, int i, int j)

    {

        char temp;

        char[] charArray = a.toCharArray();

        temp = charArray[i] ;

        charArray[i] = charArray[j];

        charArray[j] = temp;

        return String.valueOf(charArray);

    }

  
}

  
// Этот код предоставлен Михиром Джоши

питон

# Программа Python для печати всех перестановок с
# разрешено дублирование

  

def toString(List):

    return ''.join(List)

  
# Функция для печати перестановок строки
# Эта функция принимает три параметра:
# 1. Строка
# 2. Начальный индекс строки
# 3. Конечный индекс строки.

def permute(a, l, r):

    if l==r:

        print toString(a)

    else:

        for i in xrange(l,r+1):

            a[l], a[i] = a[i], a[l]

            permute(a, l+1, r)

            a[l], a[i] = a[i], a[l] # возврат

  
# Драйвер программы для проверки вышеуказанной функции

string = "ABC"

n = len(string)

a = list(string)

permute(a, 0, n-1)

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для печати всех
// перестановки данной строки.

using System;

  

class GFG

{

    / **

    * перестановочная функция

    * @param str строка для

       рассчитать перестановку для

    * @param l начальный индекс

    * @param r end index

    * /

    private static void permute(String str,

                                int l, int r)

    {

        if (l == r)

            Console.WriteLine(str);

        else

        {

            for (int i = l; i <= r; i++)

            {

                str = swap(str, l, i);

                permute(str, l + 1, r);

                str = swap(str, l, i);

            }

        }

    }

  

    / **

    * Обмен персонажей на позиции

    * @param строковое значение

    * @param I позиция 1

    * @парам j позиция 2

    * @return поменялась строка

    * /

    public static String swap(String a, 

                              int i, int j)

    {

        char temp;

        char[] charArray = a.ToCharArray();

        temp = charArray[i] ;

        charArray[i] = charArray[j];

        charArray[j] = temp;

        string s = new string(charArray);

        return s;

    }

  
// Код драйвера

public static void Main()

{

    String str = "ABC";

    int n = str.Length;

    permute(str, 0, n-1);

}
}

  
// Этот код предоставлен mits

PHP

<?php
// PHP программа для печати всего
// перестановки данной строки.

  

  
/ **
* перестановочная функция
* @param str строка для
* рассчитать перестановку для
* @param l начальный индекс
* @param r end index
* /

function permute($str, $l, $r)

{

    if ($l == $r)

        echo $str. "\n";

    else

    {

        for ($i = $l; $i <= $r; $i++)

        {

            $str = swap($str, $l, $i);

            permute($str, $l + 1, $r);

            $str = swap($str, $l, $i);

        }

    }

}

  
/ **
* Обмен персонажей на позиции
* @param строковое значение
* @param I позиция 1
* @парам j позиция 2
* @return поменялась строка
* /

function swap($a, $i, $j)

{

    $temp;

    $charArray = str_split($a);

    $temp = $charArray[$i] ;

    $charArray[$i] = $charArray[$j];

    $charArray[$j] = $temp;

    return implode($charArray);

}

  
// Код драйвера

$str = "ABC";

$n = strlen($str);

permute($str, 0, $n - 1);

  
// Этот код предоставлен mits.
?>


Выход:

ABC
ACB
BAC
BCA
CBA
CAB


Алгоритм Парадигма:
Возвращение
Сложность времени: O (n * n!) Обратите внимание, что есть n! перестановок, и это требует O (n) времени, чтобы напечатать перестановку.

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

Вывести все различные перестановки данной строки с дубликатами.
Перестановки заданной строки с использованием STL

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

Рекомендуемые посты:

Напишите программу для печати всех перестановок данной строки

0.00 (0%) 0 votes