Posted on by Kalkicode
Code Backtracking

# Generate permutations with only adjacent swaps allowed

Permutations are rearrangements of a set of elements. In the case of a string, the elements are the characters that make up the string. Adjacent swaps are a type of permutation where only adjacent elements can be swapped. This means that if we have a string of length n, we can only swap adjacent pairs of elements.

For example

``````
Example 1
ABCDE <-- Given
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED

Example 2
ABCD <-- Given
ABDC
ACBD
BACD
``````

## Code Solution

``````// C Program
// Generate permutations with only adjacent swaps allowed
#include <stdio.h>
#include <string.h>

// Display result
void printSequence(char result[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%c", result[i]);
}
printf("\n");
}
void findPermutation(char *text,
char result[], int index, int n)
{
if (index == n)
{
printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text[index];
findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text[index + 1];
result[index + 1] = text[index];
}
findPermutation(text, result, index + 2, n);
}
void permutation(char *text)
{
int n = strlen(text);
if (n == 0)
{
return;
}
// Collect result
char result[n];
// Test
findPermutation(text, result, 0, n);
}
int main()
{
permutation("ABCDE");
return 0;
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````/*
Java program
Generate permutations with only adjacent swaps allowed
*/
public class Permutations
{
// Display result
public void printSequence(char[] result, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(result[i]);
}
System.out.print("\n");
}
public void findPermutation(String text,
char[] result, int index, int n)
{
if (index == n)
{
printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text.charAt(index);
findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text.charAt(index + 1);
result[index + 1] = text.charAt(index);
}
findPermutation(text, result, index + 2, n);
}
public void permutation(String text)
{
int n = text.length();
if (n == 0)
{
return;
}
// Collect result
char[] result = new char[n];
// Find
findPermutation(text, result, 0, n);
}
public static void main(String[] args)
{
// Test
}
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program
Generate permutations with only adjacent swaps allowed
*/
class Permutations
{
public:
// Display result
void printSequence(char result[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << result[i];
}
cout << "\n";
}
void findPermutation(string text,
char result[], int index, int n)
{
if (index == n)
{
this->printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text[index];
this->findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text[index + 1];
result[index + 1] = text[index];
}
this->findPermutation(text, result, index + 2, n);
}
void permutation(string text)
{
int n = text.length();
if (n == 0)
{
return;
}
// Collect result
char result[n];
// Find
this->findPermutation(text, result, 0, n);
}
};
int main()
{
// Test
return 0;
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````// Include namespace system
using System;
/*
Csharp program
Generate permutations with only adjacent swaps allowed
*/
public class Permutations
{
// Display result
public void printSequence(char[] result, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(result[i]);
}
Console.Write("\n");
}
public void findPermutation(String text,
char[] result,
int index,
int n)
{
if (index == n)
{
this.printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text[index];
this.findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text[index + 1];
result[index + 1] = text[index];
}
this.findPermutation(text, result, index + 2, n);
}
public void permutation(String text)
{
int n = text.Length;
if (n == 0)
{
return;
}
// Collect result
char[] result = new char[n];
// Find
this.findPermutation(text, result, 0, n);
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````package main
import "fmt"
/*
Go program
Generate permutations with only adjacent swaps allowed
*/
type Permutations struct {}
func getPermutations() * Permutations {
var me *Permutations = &Permutations {}
return me
}
// Display result
func(this Permutations) printSequence(result[] byte, n int) {
for i := 0 ; i < n ; i++ {
fmt.Printf("%c",result[i])
}
fmt.Print("\n")
}
func(this Permutations) findPermutation(text string,
result[] byte, index int, n int) {
if index == n {
this.printSequence(result, n)
}
if index >= n {
// Base case when stop process
return
}
// Collect index value
result[index] = text[index]
this.findPermutation(text, result, index + 1, n)
if index + 1 < n {
// Collect swap views of adjacent elements
result[index] = text[index + 1]
result[index + 1] = text[index]
}
this.findPermutation(text, result, index + 2, n)
}
func(this Permutations) permutation(text string) {
var n int = len(text)
if n == 0 {
return
}
// Collect result
var result = make([] byte, n)
// Find
this.findPermutation(text, result, 0, n)
}
func main() {
var task * Permutations = getPermutations()
// Test
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````<?php
/*
Php program
Generate permutations with only adjacent swaps allowed
*/
class Permutations
{
// Display result
public	function printSequence(\$result, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(\$result[\$i]);
}
echo("\n");
}
public	function findPermutation(\$text, \$result, \$index, \$n)
{
if (\$index == \$n)
{
\$this->printSequence(\$result, \$n);
}
if (\$index >= \$n)
{
// Base case when stop process
return;
}
// Collect index value
\$result[\$index] = \$text[\$index];
\$this->findPermutation(\$text, \$result, \$index + 1, \$n);
if (\$index + 1 < \$n)
{
// Collect swap views of adjacent elements
\$result[\$index] = \$text[\$index + 1];
\$result[\$index + 1] = \$text[\$index];
}
\$this->findPermutation(\$text, \$result, \$index + 2, \$n);
}
public	function permutation(\$text)
{
\$n = strlen(\$text);
if (\$n == 0)
{
return;
}
// Collect result
\$result = array_fill(0, \$n, ' ');
// Find
\$this->findPermutation(\$text, \$result, 0, \$n);
}
}

function main()
{
// Test
}
main();``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````/*
Node JS program
Generate permutations with only adjacent swaps allowed
*/
class Permutations
{
// Display result
printSequence(result, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(result[i]);
}
process.stdout.write("\n");
}
findPermutation(text, result, index, n)
{
if (index == n)
{
this.printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text.charAt(index);
this.findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text.charAt(index + 1);
result[index + 1] = text.charAt(index);
}
this.findPermutation(text, result, index + 2, n);
}
permutation(text)
{
var n = text.length;
if (n == 0)
{
return;
}
// Collect result
var result = Array(n).fill(' ');
// Find
this.findPermutation(text, result, 0, n);
}
}

function main()
{
// Test
}
main();``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````#    Python 3 program
#    Generate permutations with only adjacent swaps allowed
class Permutations :
#  Display result
def printSequence(self, result, n) :
i = 0
while (i < n) :
print(result[i], end = "")
i += 1

print(end = "\n")

def findPermutation(self, text, result, index, n) :
if (index == n) :
self.printSequence(result, n)

if (index >= n) :
#  Base case when stop process
return

#  Collect index value
result[index] = text[index]
self.findPermutation(text, result, index + 1, n)
if (index + 1 < n) :
#  Collect swap views of adjacent elements
result[index] = text[index + 1]
result[index + 1] = text[index]

self.findPermutation(text, result, index + 2, n)

def permutation(self, text) :
n = len(text)
if (n == 0) :
return

#  Collect result
result = [ ' ' ] * (n)
#  Find
self.findPermutation(text, result, 0, n)

def main() :
#  Test

if __name__ == "__main__": main()``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````#    Ruby program
#    Generate permutations with only adjacent swaps allowed
class Permutations
#  Display result
def printSequence(result, n)
i = 0
while (i < n)
print(result[i])
i += 1
end

print("\n")
end

def findPermutation(text, result, index, n)
if (index == n)
self.printSequence(result, n)
end

if (index >= n)
#  Base case when stop process
return
end

#  Collect index value
result[index] = text[index]
self.findPermutation(text, result, index + 1, n)
if (index + 1 < n)
#  Collect swap views of adjacent elements
result[index] = text[index + 1]
result[index + 1] = text[index]
end

self.findPermutation(text, result, index + 2, n)
end

def permutation(text)
n = text.length
if (n == 0)
return
end

#  Collect result
result = Array.new(n) {' '}
#  Find
self.findPermutation(text, result, 0, n)
end

end

def main()
#  Test
end

main()``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````
``````import scala.collection.mutable._;
/*
Scala program
Generate permutations with only adjacent swaps allowed
*/
class Permutations()
{
// Display result
def printSequence(result: Array[Char],
n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(result(i));
i += 1;
}
print("\n");
}
def findPermutation(text: String,
result: Array[Char],
index: Int, n: Int): Unit = {
if (index == n)
{
printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result(index) = text.charAt(index);
findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result(index) = text.charAt(index + 1);
result(index + 1) = text.charAt(index);
}
findPermutation(text, result, index + 2, n);
}
def permutation(text: String): Unit = {
var n: Int = text.length();
if (n == 0)
{
return;
}
// Collect result
var result: Array[Char] = Array.fill[Char](n)(' ');
// Find
findPermutation(text, result, 0, n);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Permutations = new Permutations();
// Test
}
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````import Foundation;
/*
Swift 4 program
Generate permutations with only adjacent swaps allowed
*/
class Permutations
{
// Display result
func printSequence(_ result: [Character], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(result[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func findPermutation(_ text: [Character],
_ result: inout[Character],
_ index: Int, _ n: Int)
{
if (index == n)
{
self.printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text[index];
self.findPermutation(text, &result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text[index + 1];
result[index + 1] = text[index];
}
self.findPermutation(text, &result, index + 2, n);
}
func permutation(_ text: String)
{
let n: Int = text.count;
if (n == 0)
{
return;
}
// Collect result
var result: [Character] = Array(repeating: " ", count: n);
// Find
self.findPermutation(Array(text), &result, 0, n);
}
}
func main()
{
// Test
}
main();``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED
``````/*
Kotlin program
Generate permutations with only adjacent swaps allowed
*/
class Permutations
{
// Display result
fun printSequence(result: Array < Char > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(result[i]);
i += 1;
}
print("\n");
}
fun findPermutation(text: String,
result: Array < Char > ,
index: Int, n: Int): Unit
{
if (index == n)
{
this.printSequence(result, n);
}
if (index >= n)
{
// Base case when stop process
return;
}
// Collect index value
result[index] = text.get(index);
this.findPermutation(text, result, index + 1, n);
if (index + 1 < n)
{
// Collect swap views of adjacent elements
result[index] = text.get(index + 1);
result[index + 1] = text.get(index);
}
this.findPermutation(text, result, index + 2, n);
}
fun permutation(text: String): Unit
{
val n: Int = text.length;
if (n == 0)
{
return;
}
// Collect result
var result: Array < Char > = Array(n)
{
' '
};
// Find
this.findPermutation(text, result, 0, n);
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

``````ABCDE
ABCED
ABDCE
ACBDE
ACBED
BACDE
BACED

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post