Рубрики

Генерация перестановок только с разрешенными соседними перестановками

Имеется строка длиной N. Вы можете поменять местами только соседние элементы, и каждый элемент можно поменять местами не более одного раза. Найдите количество перестановок строки, которые могут быть сгенерированы после выполнения перестановок, как уже упоминалось.

Примеры:

Input : 12345
Output : 12345 12354 12435 13245 13254 
         21345 21354 21435

Источник: Goldman Sachs Интервью

Рассмотрим любой i-й символ в строке. У этого персонажа есть две возможности:
1.) Не меняйте его, то есть не делайте ничего с этим персонажем и переходите к следующему персонажу.
2.) Поменяйте местами. Как это можно поменять местами с соседними,
…… ..a.) Поменяйте местами следующий символ. Поскольку каждый символ можно поменять местами максимум один раз, мы переместимся в позицию (i + 2).
……. б.) Поменяйте местами с предыдущим символом — нам не нужно отдельно рассматривать этот случай, так как i-й символ — это следующий символ (i-1) -го, который аналогичен случаю 2.a.

C ++

// Программа CPP для генерации перестановок только с
// один обмен разрешен.
#include <cstring>
#include <iostream>

using namespace std;

  

void findPermutations(char str[], int index, int n)

{

    if (index >= n || (index + 1) >= n) {

        cout << str << endl;

        return;

    }

  

    // не меняем текущую позицию

    findPermutations(str, index + 1, n);

  

    // Меняем местами следующий символ и

    // отменить изменения. Как объяснил

    // выше, обмен с предыдущим

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

    // для следующего символа.

    swap(str[index], str[index + 1]);

    findPermutations(str, index + 2, n);

    swap(str[index], str[index + 1]);

}

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

int main()

{

    char str[] = { "12345" };

    int n = strlen(str);

    findPermutations(str, 0, n);

    return 0;

}

Джава

// Java-программа для генерации перестановок только с
// один обмен разрешен.

  

class GFG {

  

    static void findPermutations(char str[], int index, int n) {

        if (index >= n || (index + 1) >= n) {

            System.out.println(str);

            return;

        }

  

        // не меняем текущую позицию

        findPermutations(str, index + 1, n);

  

        // Меняем местами следующий символ и

        // отменить изменения. Как объяснил

        // выше, обмен с предыдущим

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

        // для следующего символа.

        swap(str, index);

        findPermutations(str, index + 2, n);

        swap(str, index);

    }

  

    static void swap(char arr[], int index) {

        char temp = arr[index];

        arr[index] = arr[index + 1];

        arr[index + 1] = temp;

    }

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

  

    public static void main(String[] args) {

        char str[] = "12345".toCharArray();

        int n = str.length;

        findPermutations(str, 0, n);

    }

}
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для генерации перестановок
# допускается только один обмен.

def findPermutations(string, index, n):

    if index >= n or (index + 1) >= n:

        print(''.join(string))

        return

  

    # не меняйте текущую позицию

    findPermutations(string, index + 1, n)

  

    # Поменяйте местами следующий символ и

    # отменить изменения. Как объяснил

    # выше, обмен с предыдущим

    # не нужно, как это все равно бывает

    # для следующего персонажа.

    string[index], \

    string[index + 1] = string[index + 1], \

                        string[index]

                          

    findPermutations(string, index + 2, n)

      

    string[index], \

    string[index + 1] = string[index + 1], \

                        string[index]

  
Код водителя

if __name__ == "__main__":

    string = list("12345")

    n = len(string)

    findPermutations(string, 0, n)

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

C #

// C # программа для генерации перестановок только с
// один обмен разрешен.

using System; 

public class GFG { 

  

    static void findPermutations(char []str, int index, int n) { 

        if (index >= n || (index + 1) >= n) { 

            Console.WriteLine(str); 

            return

        

  

        // не меняем текущую позицию

        findPermutations(str, index + 1, n); 

  

        // Меняем местами следующий символ и

        // отменить изменения. Как объяснил

        // выше, обмен с предыдущим

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

        // для следующего символа.

        swap(str, index); 

        findPermutations(str, index + 2, n); 

        swap(str, index); 

    

  

    static void swap(char []arr, int index) { 

        char temp = arr[index]; 

        arr[index] = arr[index + 1]; 

        arr[index + 1] = temp; 

    

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

  

    public static void Main() { 

        char []str = "12345".ToCharArray(); 

        int n = str.Length; 

        findPermutations(str, 0, n); 

    

  
// Этот код предоставлен Rajput-Ji

PHP

<?php
// PHP программа для генерации перестановок
// разрешен только один обмен.

  

function findPermutations($str, $index, $n

    if ($index >= $n || ($index + 1) >= $n

    

        echo $str, "\n"

        return

    

  

    // не меняем текущую позицию

    findPermutations($str, $index + 1, $n); 

  

    // Меняем местами следующий символ и

    // отменить изменения. Как объяснил

    // выше, обмен с предыдущим

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

    // для следующего символа.

    list($str[$index], 

         $str[$index + 1]) = array($str[$index + 1], 

                                   $str[$index]);

  

    findPermutations($str, $index + 2, $n); 

    list($str[$index], 

         $str[$index + 1]) = array($str[$index + 1],

                                   $str[$index]);

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

$str = "12345"

$n = strlen($str); 

findPermutations($str, 0, $n); 

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


Выход:

12345
12354
12435
13245
13254
21345
21354
21435

Эта статья предоставлена ekta1994 . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Генерация перестановок только с разрешенными соседними перестановками

0.00 (0%) 0 votes