Programa C++ para imprimir todas las permutaciones de una string dada

Una permutación también llamada «número de arreglo» u «orden» es un reordenamiento de los elementos de una lista ordenada S en una correspondencia uno a uno con S mismo. ¡Una string de longitud n tiene n! permutación. 

Fuente: Mathword ( http://mathworld.wolfram.com/Permutation.html )

A continuación se muestran las permutaciones de la string ABC. 
ABC ACB BAC BCA CBA CABINA

Aquí hay una solución que se usa como base en el retroceso.

// C++ program to print all permutations 
// with duplicates allowed 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to print permutations 
// of string 
// This function takes three parameters: 
// 1. String 
// 2. Starting index of the string 
// 3. Ending index of the string. 
void permute(string a, int l, int r) 
{ 
    // Base case 
    if (l == r) 
        cout<<a<<endl; 
    else
    { 
        // Permutations made 
        for (int i = l; i <= r; i++) 
        { 
            // Swapping done 
            swap(a[l], a[i]); 
  
            // Recursion called 
            permute(a, l+1, r); 
  
            //backtrack 
            swap(a[l], a[i]); 
        } 
    } 
} 
  
// Driver Code 
int main() 
{ 
    string str = "ABC"; 
    int n = str.size(); 
    permute(str, 0, n-1); 
    return 0; 
} 
// This is code is contributed by rathbhupendra 

Producción: 

ABC
ACB
BAC
BCA
CBA
CAB

Paradigma de algoritmo: retroceso 

Complejidad de tiempo: O(n*n!) Tenga en cuenta que hay n! permutaciones y requiere O(n) tiempo para imprimir una permutación.

Espacio Auxiliar: O(r – l)

Nota: La solución anterior imprime permutaciones duplicadas si hay caracteres repetidos en la string de entrada. Consulte el enlace a continuación para obtener una solución que imprima solo permutaciones distintas, incluso si hay duplicados en la entrada.
Imprime todas las permutaciones distintas de una string dada con duplicados.  
Permutaciones de una string dada usando STL

Otro enfoque:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#include <string>
using namespace std;
  
void permute(string s, 
             string answer)
{
    if(s.length() == 0)
    {
        cout << answer << "  ";
        return;
    }
    for(int i = 0; 
            i < s.length(); i++)
    {
        char ch = s[i];
        string left_substr = s.substr(0, i);
        string right_substr = s.substr(i + 1);
        string rest = left_substr + right_substr;
        permute(rest , answer+ch);
    }
}
  
// Driver code
int main()
{
    string s;
    string answer = "";
  
    cout << "Enter the string : ";
    cin >> s;
  
    cout << 
    "All possible strings are : ";
    permute(s, answer);
    return 0;
}

Producción:

Enter the string : abc
All possible strings are : abc  acb  bac  bca  cab  cba

Complejidad de tiempo: O(n*n!) La complejidad de tiempo es la misma que en el enfoque anterior, es decir, ¡hay n! permutaciones y requiere O(n) tiempo para imprimir una permutación.

Espacio Auxiliar: O(|s|)

Consulte el artículo completo sobre Escribir un programa para imprimir todas las permutaciones de una string determinada para obtener más detalles.