Generate permutations with only adjacent swaps allowed

0 0 4 minutes read

Given a string on length N. You can swap only the adjacent elements and each element can be swapped atmost once. Find the no of permutations of the string that can be generated after performing the swaps as mentioned.

Examples:

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

Source: Goldman Sachs Interview

Consider any i-th character in the string. There are two possibilities for this character:

Don’t swap it, i.e. don’t do anything with this character and move to the next character.
Swap it. As it can be swapped with its adjacent,
1. Swap it with the next character. Because each character can be swapped atmost once, we’ll move to the position (i+2).
2. Swap it with the previous character – we don’t need to consider this case separately as i-th character is the next character of (i-1)th which is same as the case 2.a.

Implementation:

C++

// CPP program to generate permutations with only
// one swap allowed.
#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;
    }
 
    // don't swap the current position
    findPermutations(str, index + 1, n);
 
    // Swap with the next character and
    // revert the changes. As explained
    // above, swapping with previous is
    // is not needed as it anyways happens
    // for next character.
    swap(str[index], str[index + 1]);
    findPermutations(str, index + 2, n);
    swap(str[index], str[index + 1]);
}
 
// Driver code
int main()
{
    char str[] = { "12345" };
    int n = strlen(str);
    findPermutations(str, 0, n);
    return 0;
}

Java

// Java program to generate permutations with only
// one swap allowed.
 
class GFG {
 
    static void findPermutations(char str[], int index, int n) {
        if (index >= n || (index + 1) >= n) {
            System.out.println(str);
            return;
        }
 
        // don't swap the current position
        findPermutations(str, index + 1, n);
 
        // Swap with the next character and
        // revert the changes. As explained
        // above, swapping with previous is
        // is not needed as it anyways happens
        // for next character.
        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;
    }
// Driver code
 
    public static void main(String[] args) {
        char str[] = "12345".toCharArray();
        int n = str.length;
        findPermutations(str, 0, n);
    }
}
// This code is contributed by 29AjayKumar

Python3

# Python3 program to generate permutations 
# with only one swap allowed.
def findPermutations(string, index, n):
    if index >= n or (index + 1) >= n:
        print(''.join(string))
        return
 
    # don't swap the current position
    findPermutations(string, index + 1, n)
 
    # Swap with the next character and
    # revert the changes. As explained
    # above, swapping with previous is
    # is not needed as it anyways happens
    # for next character.
    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]
 
# Driver Code
if __name__ == "__main__":
    string = list("12345")
    n = len(string)
    findPermutations(string, 0, n)
 
# This code is contributed by
# sanjeev2552

C#

// C# program to generate permutations with only 
// one swap allowed. 
using System; 
public class GFG { 
 
    static void findPermutations(char []str, int index, int n) { 
        if (index >= n || (index + 1) >= n) { 
            Console.WriteLine(str); 
            return; 
        } 
 
        // don't swap the current position 
        findPermutations(str, index + 1, n); 
 
        // Swap with the next character and 
        // revert the changes. As explained 
        // above, swapping with previous is 
        // is not needed as it anyways happens 
        // for next character. 
        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; 
    } 
// Driver code 
 
    public static void Main() { 
        char []str = "12345".ToCharArray(); 
        int n = str.Length; 
        findPermutations(str, 0, n); 
    } 
} 
 
// This code is contributed by Rajput-Ji

PHP

<?php
// PHP program to generate permutations
// with only one swap allowed. 
 
function findPermutations($str, $index, $n) 
{ 
    if ($index >= $n || ($index + 1) >= $n) 
    { 
        echo $str, "\n"; 
        return; 
    } 
 
    // don't swap the current position 
    findPermutations($str, $index + 1, $n); 
 
    // Swap with the next character and 
    // revert the changes. As explained 
    // above, swapping with previous is 
    // is not needed as it anyways happens 
    // for next character. 
    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]);
} 
 
// Driver code 
$str = "12345" ; 
$n = strlen($str); 
findPermutations($str, 0, $n); 
 
// This code is contributed by Sach_Code
?>

Javascript

<script>
 
      // JavaScript program to generate 
      // permutations with only
      // one swap allowed.
      function findPermutations(str, index, n) {
        if (index >= n || index + 1 >= n) {
          document.write(str.join("") + "<br>");
          return;
        }
 
        // don't swap the current position
        findPermutations(str, index + 1, n);
 
        // Swap with the next character and
        // revert the changes. As explained
        // above, swapping with previous is
        // is not needed as it anyways happens
        // for next character.
        swap(str, index);
        findPermutations(str, index + 2, n);
        swap(str, index);
      }
 
      function swap(arr, index) {
        var temp = arr[index];
        arr[index] = arr[index + 1];
        arr[index + 1] = temp;
      }
      // Driver code
 
      var str = "12345".split("");
      var n = str.length;
      findPermutations(str, 0, n);
       
</script>

Output

This article is contributed by ekta1994. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!