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 
// of a given string. 
using System; 
  
class GFG 
{ 
    /* Permutation function @param 
       str string to calculate permutation 
       for @param l starting index @param 
       r end index */
    private static void permute(String str, 
                                int l, int r) 
    { 
        if (l == r) 
            Console.WriteLine(str); 
        else
        { 
            for (int i = l; i <= r; i++) 
            { 
                str = swap(str, l, i); 
                permute(str, l + 1, r); 
                str = swap(str, l, i); 
            } 
        } 
    } 
  
    /* Swap Characters at position 
       @param a string value @param 
       i position 1 @param j position 2 
       @return swapped string */
    public static String swap(String a, 
                            int i, int j) 
    { 
        char temp; 
        char[] charArray = a.ToCharArray(); 
        temp = charArray[i] ; 
        charArray[i] = charArray[j]; 
        charArray[j] = temp; 
        string s = new string(charArray); 
        return s; 
    } 
  
// Driver Code 
public static void Main() 
{ 
    String str = "ABC"; 
    int n = str.Length; 
    permute(str, 0, n-1); 
} 
} 
// This code is contributed by mits 

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
using System;
public class GFG{
   
static void permute(String s,
                    String answer)
{   
    if (s.Length == 0)
    {
        Console.Write(answer + "  ");
        return;
    }
      
    for(int i = 0 ;i < s.Length; i++)
    {
        char ch = s[i];
        String left_substr = s.Substring(0, i);
        String right_substr = s.Substring(i + 1);
        String rest = left_substr + right_substr;
        permute(rest, answer + ch);
    }
}
  
// Driver code
public static void Main(String []args)
{    
    String s;
    String answer="";
      
    Console.Write(
    "Enter the string : ");
    s = Console.ReadLine();
      
    Console.Write(
    "\nAll possible strings are : ");
    permute(s, answer);
}
}
// This code is contributed by gauravrajput1 

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.