Listado de todas las permutaciones de una cadena / entero

Una tarea común en la progtwigción de entrevistas (aunque no por mi experiencia de entrevistas) es tomar una cadena o un número entero y enumerar cada permutación posible.

¿Hay un ejemplo de cómo se hace esto y la lógica detrás de la solución de ese problema?

He visto algunos fragmentos de código pero no fueron bien comentados / explicados y, por lo tanto, difíciles de seguir.

En primer lugar, ¡huele a recursión, por supuesto!

Como también querías saber el principio, hice todo lo posible por explicarle el lenguaje humano. Creo que la recursión es muy fácil la mayoría de las veces. Solo tiene que comprender dos pasos:

  1. El primer paso
  2. Todos los otros pasos (todos con la misma lógica)

En lenguaje humano :

En breve:
1. La permutación de 1 elemento es un elemento.
2. La permutación de un conjunto de elementos es una lista de cada uno de los elementos, concatenada con cada permutación de los otros elementos.

Ejemplo:

Si el conjunto solo tiene un elemento ->
devolverlo.
permanente (a) -> a

Si el conjunto tiene dos caracteres: para cada elemento en él: devuelve el elemento, con la permutación del rest de los elementos añadidos, así:

permanente (ab) ->

a + permanente (b) -> ab

b + permanente (a) -> ba

Además: para cada personaje en el conjunto: devuelve un carácter, concatenado con una perumación de> el rest del conjunto

permanente (abc) ->

a + permanente (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> cab , cba

permanente (abc … z) ->

a + permanente (…), b + permanente (….)
….

Encontré el pseudocódigo en http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ :

makePermutations(permutation) { if (length permutation < required length) { for (i = min digit to max digit) { if (i not in permutation) { makePermutations(permutation+i) } } } else { add permutation to list } } 

DO#

OK, y algo más elaborado (y dado que está etiquetado c #), de http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : bastante largo, pero decidí copiarlo De todas formas, la publicación no depende del original.

La función toma una cadena de caracteres, y anota cada permutación posible de esa cadena exacta, por lo que, por ejemplo, si se ha suministrado "ABC", debería dertwigrse:

ABC, ACB, BAC, BCA, CAB, CBA.

Código:

 class Program { private static void Swap(ref char a, ref char b) { if (a == b) return; a ^= b; b ^= a; a ^= b; } public static void GetPer(char[] list) { int x = list.Length - 1; GetPer(list, 0, x); } private static void GetPer(char[] list, int k, int m) { if (k == m) { Console.Write(list); } else for (int i = k; i <= m; i++) { Swap(ref list[k], ref list[i]); GetPer(list, k + 1, m); Swap(ref list[k], ref list[i]); } } static void Main() { string str = "sagiv"; char[] arr = str.ToCharArray(); GetPer(arr); } } 

Son solo dos líneas de código si LINQ puede usar. Por favor mira mi respuesta aquí .

EDITAR

Aquí está mi función genérica que puede devolver todas las permutaciones (no combinaciones) de una lista de T:

 static IEnumerable> GetPermutations(IEnumerable list, int length) { if (length == 1) return list.Select(t => new T[] { t }); return GetPermutations(list, length - 1) .SelectMany(t => list.Where(e => !t.Contains(e)), (t1, t2) => t1.Concat(new T[] { t2 })); } 

Ejemplo:

 IEnumerable> result = GetPermutations(Enumerable.Range(1, 3), 3); 

Salida – una lista de listas enteras:

 {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1} 

Como esta función usa LINQ entonces requiere .net 3.5 o superior.

Aquí he encontrado la solución. Fue escrito en Java, pero lo he convertido en C #. Espero que te ayude.

Ingrese la descripción de la imagen aquí

Aquí está el código en C #:

 static void Main(string[] args) { string str = "ABC"; char[] charArry = str.ToCharArray(); permute(charArry, 0, 2); Console.ReadKey(); } static void permute(char[] arry, int i, int n) { int j; if (i==n) Console.WriteLine(arry); else { for(j = i; j <=n; j++) { swap(ref arry[i],ref arry[j]); permute(arry,i+1,n); swap(ref arry[i], ref arry[j]); //backtrack } } } static void swap(ref char a, ref char b) { char tmp; tmp = a; a=b; b = tmp; } 

La recursividad no es necesaria, aquí hay buena información sobre esta solución.

 var values1 = new[] { 1, 2, 3, 4, 5 }; foreach (var permutation in values1.GetPermutations()) { Console.WriteLine(string.Join(", ", permutation)); } var values2 = new[] { 'a', 'b', 'c', 'd', 'e' }; foreach (var permutation in values2.GetPermutations()) { Console.WriteLine(string.Join(", ", permutation)); } Console.ReadLine(); 

Me han utilizado este algoritmo durante años, tiene O (N) el tiempo y la complejidad del espacio para calcular cada permutación .

 public static class SomeExtensions { public static IEnumerable> GetPermutations(this IEnumerable enumerable) { var array = enumerable as T[] ?? enumerable.ToArray(); var factorials = Enumerable.Range(0, array.Length + 1) .Select(Factorial) .ToArray(); for (var i = 0L; i < factorials[array.Length]; i++) { var sequence = GenerateSequence(i, array.Length - 1, factorials); yield return GeneratePermutation(array, sequence); } } private static IEnumerable GeneratePermutation(T[] array, IReadOnlyList sequence) { var clone = (T[]) array.Clone(); for (int i = 0; i < clone.Length - 1; i++) { Swap(ref clone[i], ref clone[i + sequence[i]]); } return clone; } private static int[] GenerateSequence(long number, int size, IReadOnlyList factorials) { var sequence = new int[size]; for (var j = 0; j < sequence.Length; j++) { var facto = factorials[sequence.Length - j]; sequence[j] = (int)(number / facto); number = (int)(number % facto); } return sequence; } static void Swap(ref T a, ref T b) { T temp = a; a = b; b = temp; } private static long Factorial(int n) { long result = n; for (int i = 1; i < n; i++) { result = result * i; } return result; } } 
 void permute (char *str, int ptr) { int i, len; len = strlen(str); if (ptr == len) { printf ("%s\n", str); return; } for (i = ptr ; i < len ; i++) { swap (&str[ptr], &str[i]); permute (str, ptr + 1); swap (&str[ptr], &str[i]); } } 

Puede escribir su función de intercambio para intercambiar caracteres.
Esto se llamará permute (cadena, 0);

En primer lugar, los conjuntos tienen permutaciones, no cadenas o números enteros, así que supongo que quieres decir “el conjunto de caracteres en una cadena”.

Tenga en cuenta que un conjunto de tamaño n tiene n! n-permutaciones.

El siguiente pseudocódigo (de Wikipedia), llamado con k = 1 … n! dará todas las permutaciones:

 function permutation(k, s) { for j = 2 to length(s) { swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1 k := k / j; // integer division cuts off the remainder } return s; } 

Aquí está el código Python equivalente (para índices de matriz basados ​​en 0):

 def permutation(k, s): r = s[:] for j in range(2, len(s)+1): r[j-1], r[k%j] = r[k%j], r[j-1] k = k/j+1 return r 

Versión ligeramente modificada en C # que produce las permutaciones necesarias en una matriz de CUALQUIER tipo.

  // USAGE: create an array of any type, and call Permutations() var vals = new[] {"a", "bb", "ccc"}; foreach (var v in Permutations(vals)) Console.WriteLine(string.Join(",", v)); // Print values separated by comma public static IEnumerable Permutations(T[] values, int fromInd = 0) { if (fromInd + 1 == values.Length) yield return values; else { foreach (var v in Permutations(values, fromInd + 1)) yield return v; for (var i = fromInd + 1; i < values.Length; i++) { SwapValues(values, fromInd, i); foreach (var v in Permutations(values, fromInd + 1)) yield return v; SwapValues(values, fromInd, i); } } } private static void SwapValues(T[] values, int pos1, int pos2) { if (pos1 != pos2) { T tmp = values[pos1]; values[pos1] = values[pos2]; values[pos2] = tmp; } } 

Me gustó el enfoque FBryant87 ya que es simple. Desafortunadamente, le gusta que muchas otras “soluciones” no ofrezcan todas las permutaciones o, por ejemplo, un número entero si contiene el mismo dígito más de una vez. Tome 656123 como un ejemplo. La línea:

 var tail = chars.Except(new List(){c}); 

Usar Except hará que se eliminen todas las ocurrencias, es decir, cuando c = 6, se eliminen dos dígitos y nos quedemos con, por ejemplo, 5123. Como ninguna de las soluciones que intenté resolvió esto, decidí intentar resolverlo por FBryant87 ‘s. código como base. Esto es lo que se me ocurrió:

 private static List FindPermutations(string set) { var output = new List(); if (set.Length == 1) { output.Add(set); } else { foreach (var c in set) { // Remove one occurrence of the char (not all) var tail = set.Remove(set.IndexOf(c), 1); foreach (var tailPerms in FindPermutations(tail)) { output.Add(c + tailPerms); } } } return output; } 

Simplemente elimino la primera aparición encontrada usando .Remove y .IndexOf. Parece que funciona según lo previsto para mi uso al menos. Estoy seguro de que podría hacerse más inteligente.

Una cosa a tener en cuenta: la lista resultante puede contener duplicados, así que asegúrese de hacer que el método devuelva, por ejemplo, un HashSet en su lugar o eliminar los duplicados después de la devolución utilizando el método que desee.

Aquí hay un buen artículo que cubre tres algoritmos para encontrar todas las permutaciones, incluida una para encontrar la siguiente permutación.

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

C ++ y Python tienen incorporadas funciones next_permutation e itertools.permutations respectivamente.

Aquí hay una implementación de F # puramente funcional:

let factorial i = let rec fact nx = match n with | 0 -> 1 | 1 -> x | _ -> fact (n-1) (x*n) fact i 1 let swap (arr:'a array) ij = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |] let rec permutation (k:int,j:int) (r:'a array) = if j = (r.Length + 1) then r else permutation (k/j+1, j+1) (swap r (j-1) (k%j)) let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source } 

El rendimiento puede mejorarse en gran medida cambiando el intercambio para aprovechar la naturaleza mutable de las matrices CLR, pero esta implementación es segura para subprocesos con respecto a la matriz fuente y puede ser deseable en algunos contextos. Además, para matrices con más de 16 elementos, int debe reemplazarse por tipos con mayor / arbitraria precisión, ya que factorial 17 da como resultado un desbordamiento de int32.

Aquí hay una solución simple en c # usando la recursión,

 void Main() { string word = "abc"; WordPermuatation("",word); } void WordPermuatation(string prefix, string word) { int n = word.Length; if (n == 0) { Console.WriteLine(prefix); } else { for (int i = 0; i < n; i++) { WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1))); } } } 

Aquí hay una función de permutación fácil de entender para la cadena y el entero como entrada. Con esto , incluso puede establecer su longitud de salida (que en el caso normal es igual a la longitud de entrada)

Cuerda

  static ICollection result; public static ICollection GetAllPermutations(string str, int outputLength) { result = new List(); MakePermutations(str.ToCharArray(), string.Empty, outputLength); return result; } private static void MakePermutations( char[] possibleArray,//all chars extracted from input string permutation, int outputLength//the length of output) { if (permutation.Length < outputLength) { for (int i = 0; i < possibleArray.Length; i++) { var tempList = possibleArray.ToList(); tempList.RemoveAt(i); MakePermutations(tempList.ToArray(), string.Concat(permutation, possibleArray[i]), outputLength); } } else if (!result.Contains(permutation)) result.Add(permutation); } 

y para Entero simplemente cambia el método de llamador y MakePermutations () permanece intacto:

  public static ICollection GetAllPermutations(int input, int outputLength) { result = new List(); MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength); return result.Select(m => int.Parse(m)).ToList(); } 

ejemplo 1: GetAllPermutations (“abc”, 3); “abc” “acb” “bac” “bca” “cab” “cba”

ejemplo 2: GetAllPermutations (“abcd”, 2); “ab” “ac” “ad” “ba” “bc” “bd” “ca” “cb” “cd” “da” “db” “dc”

ejemplo 3: GetAllPermutations (486,2); 48 46 84 86 64 68

Aquí está la función que imprimirá todo permutaion. Esta función implementa la lógica Explicada por peter.

 public class Permutation { //http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm public static void permuteString(String beginningString, String endingString) { if (endingString.Length <= 1) Console.WriteLine(beginningString + endingString); else for (int i = 0; i < endingString.Length; i++) { String newString = endingString.Substring(0, i) + endingString.Substring(i + 1); permuteString(beginningString + endingString.ElementAt(i), newString); } } } static void Main(string[] args) { Permutation.permuteString(String.Empty, "abc"); Console.ReadLine(); } 

El siguiente es mi implementación de permutación. No me molestan los nombres de las variables, ya que lo estaba haciendo por diversión 🙂

 class combinations { static void Main() { string choice = "y"; do { try { Console.WriteLine("Enter word :"); string abc = Console.ReadLine().ToString(); Console.WriteLine("Combinatins for word :"); List final = comb(abc); int count = 1; foreach (string s in final) { Console.WriteLine("{0} --> {1}", count++, s); } Console.WriteLine("Do you wish to continue(y/n)?"); choice = Console.ReadLine().ToString(); } catch (Exception exc) { Console.WriteLine(exc); } } while (choice == "y" || choice == "Y"); } static string swap(string test) { return swap(0, 1, test); } static List comb(string test) { List sec = new List(); List first = new List(); if (test.Length == 1) first.Add(test); else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); } else if (test.Length > 2) { sec = generateWords(test); foreach (string s in sec) { string init = s.Substring(0, 1); string restOfbody = s.Substring(1, s.Length - 1); List third = comb(restOfbody); foreach (string s1 in third) { if (!first.Contains(init + s1)) first.Add(init + s1); } } } return first; } static string ShiftBack(string abc) { char[] arr = abc.ToCharArray(); char temp = arr[0]; string wrd = string.Empty; for (int i = 1; i < arr.Length; i++) { wrd += arr[i]; } wrd += temp; return wrd; } static List generateWords(string test) { List final = new List(); if (test.Length == 1) final.Add(test); else { final.Add(test); string holdString = test; while (final.Count < test.Length) { holdString = ShiftBack(holdString); final.Add(holdString); } } return final; } static string swap(int currentPosition, int targetPosition, string temp) { char[] arr = temp.ToCharArray(); char t = arr[currentPosition]; arr[currentPosition] = arr[targetPosition]; arr[targetPosition] = t; string word = string.Empty; for (int i = 0; i < arr.Length; i++) { word += arr[i]; } return word; } } 

Aquí hay un ejemplo de alto nivel que escribí que ilustra la explicación del lenguaje humano que Pedro dio:

  public List FindPermutations(string input) { if (input.Length == 1) return new List { input }; var perms = new List(); foreach (var c in input) { var others = input.Remove(input.IndexOf(c), 1); perms.AddRange(FindPermutations(others).Select(perm => c + perm)); } return perms; } 

Si el rendimiento y la memoria son un problema, sugiero esta implementación muy eficiente. Según el algoritmo de Heap en Wikipedia , debería ser el más rápido. Espero que se ajuste a tu necesidad :-)!

¡Así como la comparación de esto con una implementación de Linq para 10! (código incluido):

  • Esto: 36288000 elementos en 235 milisegundos
  • Linq: 36288000 artículos en 50051 milisegundos

     using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Runtime.CompilerServices; using System.Text; namespace WpfPermutations { ///  /// EO: 2016-04-14 /// Generator of all permutations of an array of anything. /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 ///  public static class Permutations { ///  /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. ///  /// Items to permute in each possible ways ///  /// Return true if cancelled public static bool ForAllPermutation(T[] items, Func funcExecuteAndTellIfShouldStop) { int countOfItem = items.Length; if (countOfItem <= 1) { return funcExecuteAndTellIfShouldStop(items); } var indexes = new int[countOfItem]; for (int i = 0; i < countOfItem; i++) { indexes[i] = 0; } if (funcExecuteAndTellIfShouldStop(items)) { return true; } for (int i = 1; i < countOfItem;) { if (indexes[i] < i) { // On the web there is an implementation with a multiplication which should be less efficient. if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same. { Swap(ref items[i], ref items[indexes[i]]); } else { Swap(ref items[i], ref items[0]); } if (funcExecuteAndTellIfShouldStop(items)) { return true; } indexes[i]++; i = 1; } else { indexes[i++] = 0; } } return false; } ///  /// This function is to show a linq way but is far less efficient ///  ///  ///  ///  ///  static IEnumerable> GetPermutations(IEnumerable list, int length) { if (length == 1) return list.Select(t => new T[] { t }); return GetPermutations(list, length - 1) .SelectMany(t => list.Where(e => !t.Contains(e)), (t1, t2) => t1.Concat(new T[] { t2 })); } ///  /// Swap 2 elements of same type ///  ///  ///  ///  [MethodImpl(MethodImplOptions.AggressiveInlining)] static void Swap(ref T a, ref T b) { T temp = a; a = b; b = temp; } ///  /// Func to show how to call. It does a little test for an array of 4 items. ///  public static void Test() { ForAllPermutation("123".ToCharArray(), (vals) => { Debug.Print(String.Join("", vals)); return false; }); int[] values = new int[] { 0, 1, 2, 4 }; Debug.Print("Non Linq"); ForAllPermutation(values, (vals) => { Debug.Print(String.Join("", vals)); return false; }); Debug.Print("Linq"); foreach(var v in GetPermutations(values, values.Length)) { Debug.Print(String.Join("", v)); } // Performance int count = 0; values = new int[10]; for(int n = 0; n < values.Length; n++) { values[n] = n; } Stopwatch stopWatch = new Stopwatch(); stopWatch.Reset(); stopWatch.Start(); ForAllPermutation(values, (vals) => { foreach(var v in vals) { count++; } return false; }); stopWatch.Stop(); Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); count = 0; stopWatch.Reset(); stopWatch.Start(); foreach (var vals in GetPermutations(values, values.Length)) { foreach (var v in vals) { count++; } } stopWatch.Stop(); Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); } } } 

Aquí está mi solución en JavaScript (NodeJS). La idea principal es que tomamos un elemento a la vez, lo “removemos” de la cadena, variamos el rest de los caracteres e insertamos el elemento al frente.

 function perms (string) { if (string.length == 0) { return []; } if (string.length == 1) { return [string]; } var list = []; for(var i = 0; i < string.length; i++) { var invariant = string[i]; var rest = string.substr(0, i) + string.substr(i + 1); var newPerms = perms(rest); for (var j = 0; j < newPerms.length; j++) { list.push(invariant + newPerms[j]); } } return list; } module.exports = perms; 

Y aquí están las pruebas:

 require('should'); var permutations = require('../src/perms'); describe('permutations', function () { it('should permute ""', function () { permutations('').should.eql([]); }) it('should permute "1"', function () { permutations('1').should.eql(['1']); }) it('should permute "12"', function () { permutations('12').should.eql(['12', '21']); }) it('should permute "123"', function () { var expected = ['123', '132', '321', '213', '231', '312']; var actual = permutations('123'); expected.forEach(function (e) { actual.should.containEql(e); }) }) it('should permute "1234"', function () { // Wolfram Alpha FTW! var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132']; var actual = permutations('1234'); expected.forEach(function (e) { actual.should.containEql(e); }) }) }) 

Aquí está la solución más simple que puedo pensar:

 let rec distribute e = function | [] -> [[e]] | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs] let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs 

La función de distribute toma un nuevo elemento e una lista de elementos n y devuelve una lista de n+1 listas, cada una de las cuales se ha insertado e en un lugar diferente. Por ejemplo, insertando 10 en cada uno de los cuatro lugares posibles en la lista [1;2;3] :

 > distribute 10 [1..3];; val it : int list list = [[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]] 

La función permute pliega sobre cada elemento distribuyéndose a lo largo de las permutaciones acumuladas hasta el momento, culminando en todas las permutaciones. Por ejemplo, las 6 permutaciones de la lista [1;2;3] :

 > permute [1;2;3];; val it : int list list = [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]] 

Cambiar el fold a un scan para mantener los acumuladores intermedios arroja algo de luz sobre cómo se generan las permutaciones de un elemento a la vez:

 > Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];; val it : seq = seq [[[]]; [[1]]; [[2; 1]; [1; 2]]; [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]] 

Enumera las permutaciones de una cadena. Evita la duplicación cuando los caracteres se repiten:

 using System; using System.Collections; class Permutation{ static IEnumerable Permutations(string word){ if (word == null || word.Length <= 1) { yield return word; yield break; } char firstChar = word[0]; foreach( string subPermute in Permutations (word.Substring (1)) ) { int indexOfFirstChar = subPermute.IndexOf (firstChar); if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length; for( int index = 0; index <= indexOfFirstChar; index++ ) yield return subPermute.Insert (index, new string (firstChar, 1)); } } static void Main(){ foreach( var permutation in Permutations ("aab") ) Console.WriteLine (permutation); } } 
 class Program { public static void Main(string[] args) { Permutation("abc"); } static void Permutation(string rest, string prefix = "") { if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix); // Each letter has a chance to be permutated for (int i = 0; i < rest.Length; i++) { Permutation(rest.Remove(i, 1), prefix + rest[i]); } } } 

Aquí está la función que imprimirá todas las permutaciones recursivamente.

 public void Permutations(string input, StringBuilder sb) { if (sb.Length == input.Length) { Console.WriteLine(sb.ToString()); return; } char[] inChar = input.ToCharArray(); for (int i = 0; i < input.Length; i++) { if (!sb.ToString().Contains(inChar[i])) { sb.Append(inChar[i]); Permutations(input, sb); RemoveChar(sb, inChar[i]); } } } private bool RemoveChar(StringBuilder input, char toRemove) { int index = input.ToString().IndexOf(toRemove); if (index >= 0) { input.Remove(index, 1); return true; } return false; } 

Aquí hay una respuesta C # que está un poco simplificada.

 public static void StringPermutationsDemo() { strBldr = new StringBuilder(); string result = Permute("ABCD".ToCharArray(), 0); MessageBox.Show(result); } static string Permute(char[] elementsList, int startIndex) { if (startIndex == elementsList.Length) { foreach (char element in elementsList) { strBldr.Append(" " + element); } strBldr.AppendLine(""); } else { for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++) { Swap(ref elementsList[startIndex], ref elementsList[tempIndex]); Permute(elementsList, (startIndex + 1)); Swap(ref elementsList[startIndex], ref elementsList[tempIndex]); } } return strBldr.ToString(); } static void Swap(ref char Char1, ref char Char2) { char tempElement = Char1; Char1 = Char2; Char2 = tempElement; } 

Salida:

 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2 

Esta es mi solución, que es fácil para mí entender

 class ClassicPermutationProblem { ClassicPermutationProblem() { } private static void PopulatePosition(List> finalList, List list, List temp, int position) { foreach (T element in list) { List currentTemp = temp.ToList(); if (!currentTemp.Contains(element)) currentTemp.Add(element); else continue; if (position == list.Count) finalList.Add(currentTemp); else PopulatePosition(finalList, list, currentTemp, position + 1); } } public static List> GetPermutations(List list) { List> results = new List>(); PopulatePosition(results, list, new List(), 1); return results; } } static void Main(string[] args) { List> results = ClassicPermutationProblem.GetPermutations(new List() { 1, 2, 3 }); } 

Aquí hay una implementación más del algo mencionado.

 public class Program { public static void Main(string[] args) { string str = "abcefgh"; var astr = new Permutation().GenerateFor(str); Console.WriteLine(astr.Length); foreach(var a in astr) { Console.WriteLine(a); } //a.ForEach(Console.WriteLine); } } class Permutation { public string[] GenerateFor(string s) { if(s.Length == 1) { return new []{s}; } else if(s.Length == 2) { return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()}; } var comb = new List(); foreach(var c in s) { string cStr = c.ToString(); var sToProcess = s.Replace(cStr,""); if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0) { var conCatStr = GenerateFor(sToProcess); foreach(var a in conCatStr) { comb.Add(c.ToString()+a); } } } return comb.ToArray(); } } 
  //Generic C# Method private static List GetPerms(T[] input, int startIndex = 0) { var perms = new List(); var l = input.Length - 1; if (l == startIndex) perms.Add(input); else { for (int i = startIndex; i <= l; i++) { var copy = input.ToArray(); //make copy var temp = copy[startIndex]; copy[startIndex] = copy[i]; copy[i] = temp; perms.AddRange(GetPerms(copy, startIndex + 1)); } } return perms; } //usages char[] charArray = new char[] { 'A', 'B', 'C' }; var charPerms = GetPerms(charArray); string[] stringArray = new string[] { "Orange", "Mango", "Apple" }; var stringPerms = GetPerms(stringArray); int[] intArray = new int[] { 1, 2, 3 }; var intPerms = GetPerms(intArray); 
 class Permutation { public static List Permutate(string seed, List lstsList) { loopCounter = 0; // string s="\w{0,2}"; var lstStrs = PermuateRecursive(seed); Trace.WriteLine("Loop counter :" + loopCounter); return lstStrs; } // Recursive function to find permutation private static List PermuateRecursive(string seed) { List lstStrs = new List(); if (seed.Length > 2) { for (int i = 0; i < seed.Length; i++) { str = Swap(seed, 0, i); PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach( s => { lstStrs.Add(str[0] + s); loopCounter++; }); ; } } else { lstStrs.Add(seed); lstStrs.Add(Swap(seed, 0, 1)); } return lstStrs; } //Loop counter variable to count total number of loop execution in various functions private static int loopCounter = 0; //Non recursive version of permuation function public static List Permutate(string seed) { loopCounter = 0; List strList = new List(); strList.Add(seed); for (int i = 0; i < seed.Length; i++) { int count = strList.Count; for (int j = i + 1; j < seed.Length; j++) { for (int k = 0; k < count; k++) { strList.Add(Swap(strList[k], i, j)); loopCounter++; } } } Trace.WriteLine("Loop counter :" + loopCounter); return strList; } private static string Swap(string seed, int p, int p2) { Char[] chars = seed.ToCharArray(); char temp = chars[p2]; chars[p2] = chars[p]; chars[p] = temp; return new string(chars); } } 
  ///  /// Print All the Permutations. ///  /// input string /// length of the string /// output string private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars) { //Means you have completed a permutation. if (outputStr.Length == NumberOfChars) { Console.WriteLine(outputStr); return; } //For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc. for(int i=0 ; i< strLength; i++) { // Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc. PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4); } }