Рубрики

Распечатать все перестановки с повторением символов

Если задана строка длины n, выведите всю перестановку данной строки. Повторение символов допускается. Распечатать эти перестановки в лексикографически отсортированном порядке
Примеры:

Input: AB
Ouput: All permutations of AB with repetition are:
      AA
      AB
      BA
      BB

Input: ABC
Output: All permutations of ABC with repetition are:
       AAA
       AAB
       AAC
       ABA
       ...
       ...
       CCB
       CCC

Для входной строки размером n будет n ^ n перестановок с разрешенным повторением. Идея состоит в том, чтобы исправить первый символ в первом индексе и рекурсивно вызвать другие последующие индексы. После печати всех перестановок, начинающихся с первого символа, зафиксируйте второй символ в первом индексе. Продолжайте эти шаги до последнего символа. Спасибо PsychoCoder за предоставление следующей реализации C.

C ++

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

using namespace std;

  

  
/ * Следующая функция используется
функция библиотеки qsort ()
отсортировать массив символов * /

int compare (const void * a, const void * b); 

  
/ * Основная функция, которая рекурсивно
печатает все повторяющиеся перестановки
данная строка. Он использует данные [] для хранения всех
перестановки одна за другой * /

void allLexicographicRecur (char *str, char* data, 

                            int last, int index) 

    int i, len = strlen(str); 

  

    // Один за другим исправляем все символы в

    // данный индекс и повторяем для

    // последующие индексы

    for ( i = 0; i < len; i++ ) 

    

        // Исправить i-й символ в индексе

        // и если это не последний

        // индексировать, затем рекурсивно вызвать

        // для более высоких показателей

        data[index] = str[i] ; 

  

        // Если это последний индекс, то

        // выводим строку, хранящуюся в

        // данные[]

        if (index == last) 

            cout << data << endl; 

        else // Рекурс для более высоких индексов

            allLexicographicRecur (str, data, last, index+1); 

    

  
/ * Эта функция сортирует входную строку,
выделить память для данных (необходимо
для всехLexicographicRecur ()) и
вызывает allLexicographicRecur () для
печать всех перестановок * /

void allLexicographic(char *str) 

    int len = strlen (str) ; 

  

    // Создать временный массив, который будет

    // использоваться allLexicographicRecur ()

    char *data = (char *) malloc (sizeof(char) * (len + 1)) ; 

    data[len] = '\0'

  

    // сортируем входную строку так, чтобы

    // мы получаем все выходные строки в

    // лексикографически отсортированный порядок

    qsort(str, len, sizeof(char), compare); 

  

    // Теперь печатаем все перестановки

    allLexicographicRecur (str, data, len-1, 0); 

  

    // Свободные данные, чтобы избежать утечки памяти

    free(data); 

  
// Необходим для библиотечной функции qsort ()

int compare (const void * a, const void * b) 

    return ( *(char *)a - *(char *)b ); 

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

int main() 

    char str[] = "ABC"

    cout << "All permutations with repetition of "<< 

                                str <<" are: "<<endl ; 

    allLexicographic(str); 

    return 0; 

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

С

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

  
/ * Следующая функция используется библиотечной функцией qsort ()

  отсортировать массив символов * /

int compare (const void * a, const void * b);

  
/ * Основная функция, которая рекурсивно печатает все повторяющиеся

   перестановки данной строки. Он использует данные [] для хранения всех

   перестановки одна за другой * /

void allLexicographicRecur (char *str, char* data, int last, int index)

{

    int i, len = strlen(str);

  

    // Один за другим фиксируем все символы по указанному индексу и повторяем

    // последующие индексы

    for ( i=0; i<len; i++ )

    {

        // Исправить i-й символ в индексе, и если это не последний

        // index затем рекурсивно вызываем более высокие индексы

        data[index] = str[i] ;

  

        // Если это последний индекс, то вывести строку, хранящуюся в

        // данные[]

        if (index == last)

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

        else // Рекурс для более высоких индексов

            allLexicographicRecur (str, data, last, index+1);

    }

}

  
/ * Эта функция сортирует входную строку, выделяет память для данных (необходимо

   для allLexicographicRecur ()) и вызывает allLexicographicRecur () для

   печать всех перестановок * /

void allLexicographic(char *str)

{

    int len = strlen (str) ;

  

    // Создание временного массива, который будет использоваться allLexicographicRecur ()

    char *data = (char *) malloc (sizeof(char) * (len + 1)) ;

    data[len] = '\0';

  

    // Сортировка входной строки так, чтобы мы получили все выходные строки в

    // лексикографически отсортированный порядок

    qsort(str, len, sizeof(char), compare);

  

    // Теперь печатаем все перестановки

    allLexicographicRecur (str, data, len-1, 0);

  

    // Свободные данные, чтобы избежать утечки памяти

    free(data);

}

  
// Необходим для библиотечной функции qsort ()

int compare (const void * a, const void * b)

{

    return ( *(char *)a - *(char *)b );

}

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

int main()

{

    char str[] = "ABC";

    printf("All permutations with repetition of %s are: \n",

            str);

    allLexicographic(str);

    return 0;

}

Джава

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

import java.util.Arrays;

  

class GFG 

{

  

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

    // все повторяющиеся перестановки данной строки.

    // Использует data [] для хранения всех перестановок одна за другой

    static void allLexicographicRecur(String str, char[] data,

                                      int last, int index) 

    {

        int length = str.length();

  

        // один за другим фиксируем все символы по указанному индексу

        // и повторяем для последующих индексов

        for (int i = 0; i < length; i++) 

        {

  

            // Исправить i-й символ в индексе и если

            // это не последний индекс

            // рекурсивный вызов для более высоких индексов

            data[index] = str.charAt(i);

  

            // Если это последний индекс, то выведите

            // строка, хранящаяся в data []

            if (index == last)

                System.out.println(new String(data));

            else

                allLexicographicRecur(str, data, last, 

                                           index + 1);

        }

    }

  

    // Эта функция сортирует входную строку, выделяет память

    // для данных (необходимо для allLexicographicRecur ()) и вызовов

    // allLexicographicRecur () для печати всех перестановок

    static void allLexicographic(String str) 

    {

        int length = str.length();

  

        // Создать временный массив, который будет использоваться

        // allLexicographicRecur ()

        char[] data = new char[length + 1];

        char[] temp = str.toCharArray();

  

        // Сортируем входную строку так, чтобы мы получили все

        // выводим строки в лексикографически отсортированном порядке

        Arrays.sort(temp);

        str = new String(temp);

  

        // Теперь печатаем все перестановки

        allLexicographicRecur(str, data, length - 1, 0);

    }

  

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

    public static void main(String[] args) 

    {

        String str = "ABC";

        System.out.printf("All permutations with "

                   "repetition of %s are: \n", str);

        allLexicographic(str);

    }

}

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

питон

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

  

def toString(List):

    return ''.join(List)

  
# Основная функция, которая рекурсивно печатает все повторяющиеся
# перестановки данной строки. Он использует данные [] для хранения
# все перестановки один за другим

def allLexicographicRecur (string, data, last, index):

    length = len(string)

  

    # Один за другим исправьте все символы с указанным индексом и

    # recur для последующих индексов

    for i in xrange(length):

  

        # Исправить i-й символ в индексе, и если это не так

        # последний индекс затем рекурсивно вызывать для более высокого

        # индексы

        data[index] = string[i]

  

        # Если это последний индекс, выведите строку

        # хранится в данных []

        if index==last:

            print toString(data)

        else:

            allLexicographicRecur(string, data, last, index+1)

  
# Эта функция сортирует входную строку, выделяет память для данных
# (необходимо для allLexicographicRecur ()) и вызовов
# allLexicographicRecur () для печати всех перестановок

def allLexicographic(string):

    length = len(string)

  

    # Создать временный массив, который будет использоваться

    # allLexicographicRecur ()

    data = [""] * (length+1)

  

    # Сортировать входную строку так, чтобы мы получили все выходные строки в

    # лексикографически отсортированный порядок

    string = sorted(string)

  

    # Теперь распечатать все перестановки

    allLexicographicRecur(string, data, length-1, 0)

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

string = "ABC"

print "All permutations with repetition of " + string + " are:"

allLexicographic(string)

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


Выход:

All permutations with repetition of ABC are: 
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC

Основы программирования на С
Бесплатный онлайн-курс GeeksforGeeks

Далее следует дерево рекурсии для входной строки «AB». Цель дерева рекурсии — помочь понять вышеописанную реализацию, так как она показывает значения различных переменных.

                              data="" 
                          /         \
                         /           \ 
                   index=0           index=0
                    i=0               i=1 
                  data="A"           data="B"
                   /   \              /    \
                 /      \            /      \
              index=1  index=1    index=1    index=1 
               i=0      i=1        i=0        i=1 
            data="AA"  data="AB"  data="BA"  data="BB"

В приведенной выше реализации предполагается, что все символы входной строки различны. Реализация может быть легко изменена для обработки повторяющихся символов. Мы должны добавить шаг предварительной обработки для поиска уникальных символов (перед вызовом allLexicographicRecur ()).

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

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

Распечатать все перестановки с повторением символов

0.00 (0%) 0 votes