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

30.12.2019Комбинаторика, Строки

Имеется строка длиной 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
?>

Выход:

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

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

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

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

0.00 (0%) 0 votes