Genere permutaciones con solo intercambios adyacentes permitidos

Dada una string de longitud N. Puede intercambiar solo los elementos adyacentes y cada elemento puede intercambiarse al menos una vez. Encuentre el número de permutaciones de la string que se pueden generar después de realizar los intercambios como se mencionó.

Ejemplos: 

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

Fuente: Entrevista de Goldman Sachs

Considere cualquier i-ésimo carácter en la string. Hay dos posibilidades para este personaje: 

1. No lo intercambies, es decir, no hagas nada con este carácter y pasa al siguiente carácter. 
2.  cámbialo Como se puede intercambiar con su adyacente, 
   1. Cámbialo con el siguiente carácter. Debido a que cada carácter se puede intercambiar como máximo una vez, nos moveremos a la posición (i+2). 
   2. Cámbielo con el carácter anterior; no necesitamos considerar este caso por separado, ya que el i-ésimo carácter es el siguiente carácter de (i-1)-ésimo, que es el mismo que el caso 2.a.

Implementación:

// 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 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 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# 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 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
?>

<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>

12345
12354
12435
13245
13254
21345
21354
21435

Este artículo es una contribución de ekta1994 . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.