Listando todas as permutações de uma string / inteiro

Uma tarefa comum em entrevistas de programação (não da minha experiência de entrevistas) é pegar uma string ou um inteiro e listar todas as permutações possíveis.

Existe um exemplo de como isso é feito e a lógica por trás da solução de tal problema?

Eu vi alguns trechos de código, mas eles não foram bem comentados / explicados e, portanto, difíceis de seguir.

Primeiro de tudo: cheira a recursion, é claro!

Como você também queria conhecer o princípio, fiz o melhor que pude para explicar a linguagem humana. Eu acho que a recursion é muito fácil na maioria das vezes. Você só precisa entender dois passos:

  1. O primeiro passo
  2. Todos os outros passos (todos com a mesma lógica)

Na linguagem humana :

Em resumo:
1. A permutação de 1 elemento é um elemento.
2. A permutação de um conjunto de elementos é uma lista de cada um dos elementos, concatenados com cada permutação dos outros elementos.

Exemplo:

Se o conjunto tiver apenas um elemento ->
devolver.
perm (a) -> a

Se o conjunto tiver dois caracteres: para cada elemento: retorne o elemento, com a permutação do restante dos elementos adicionados, da seguinte forma:

perm (ab) ->

a + perm (b) -> ab

b + perm (a) -> ba

Além disso: para cada caractere no conjunto: retorne um caractere, concatenado com uma perumation> o restante do conjunto

perm (abc) ->

a + perm (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> cab , cba

perm (abc … z) ->

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

Eu encontrei o pseudocódigo em 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 } } 

C #

OK, e algo mais elaborado (e desde que é marcado c #), de http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : bastante demorado, mas eu decidi copiá-lo De qualquer forma, o post não depende do original.

A function recebe uma sequência de caracteres e anota todas as permutações possíveis dessa sequência exata, portanto, por exemplo, se "ABC" tiver sido fornecido, deverá aparecer:

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); } } 

São apenas duas linhas de código se o LINQ tiver permissão para usar. Por favor, veja minha resposta aqui .

EDITAR

Aqui está minha function genérica que pode retornar todas as permutações (não combinações) de uma 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 })); } 

Exemplo:

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

Saída – uma lista de listas inteiras:

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

Como esta function usa o LINQ, é necessário o .net 3.5 ou superior.

Aqui encontrei a solução. Foi escrito em Java, mas eu o converti em C #. Espero que isso ajude você.

Digite a descrição da imagem aqui

Aqui está o código em 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; } 

Recursão não é necessária, aqui está uma boa informação sobre esta solução.

 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(); 

Eu tenho usado esse algoritmo por anos, ele tem complexidade de tempo e espaço O (N) para calcular cada permutação .

 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]); } } 

Você pode escrever sua function de troca para trocar caracteres.
Isso deve ser chamado de permute (string, 0);

Primeiro de tudo, os conjuntos têm permutações, não seqüências de caracteres ou inteiros, então eu vou apenas assumir que você quer dizer “o conjunto de caracteres em uma seqüência de caracteres”.

Note que um conjunto de tamanho n tem n! n-permutações.

O seguinte pseudocódigo (da Wikipedia), chamado com k = 1 … n! dará todas as permutações:

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

Aqui está o código Python equivalente (para índices de array baseados em 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 

Versão ligeiramente modificada em C # que produz permutações necessárias em uma matriz de qualquer 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; } } 

Eu gostei da abordagem do FBryant87 já que é simples. Infelizmente, ele faz como muitas outras “soluções” não oferecem todas as permutações ou, por exemplo, um inteiro se ele contiver o mesmo dígito mais de uma vez. Tome 656123 como um exemplo. A linha:

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

Usando Exceto fará com que todas as ocorrências sejam removidas, ou seja, quando c = 6, dois dígitos serão removidos e ficaremos com, por exemplo, 5123. Como nenhuma das soluções que tentei resolveu isso, decidi tentar resolvê-lo por FBryant87 . código como base. Isto é o que eu criei:

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

Eu simplesmente removo a primeira ocorrência encontrada usando .Remove e .IndexOf. Parece funcionar como pretendido pelo menos para o meu uso. Tenho certeza de que poderia ser mais inteligente.

Uma coisa a notar é que: A lista resultante pode conter duplicatas, portanto, certifique-se de fazer o método retornar, por exemplo, um HashSet ou remover as duplicatas após o retorno usando qualquer método que desejar.

Aqui está um bom artigo cobrindo três algoritmos para encontrar todas as permutações, incluindo uma para encontrar a próxima permutação.

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

C ++ e Python possuem funções de next_permutation e itertools.permutations , respectivamente.

Aqui está uma implementação 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 } 

O desempenho pode ser bastante aprimorado alterando-se a troca para aproveitar a natureza mutável dos arrays do CLR, mas essa implementação é thread-safe em relação ao array de origem e que pode ser desejável em alguns contextos. Além disso, para matrizes com mais de 16 elementos int devem ser substituídos por tipos com maior / arbitrária precisão como fatorial 17 resulta em um estouro de int32.

Aqui está uma function de permuta fácil de entender para string e inteiro como input. Com isso, você pode até definir o seu comprimento de saída (que, no caso normal, é igual ao comprimento de input)

Corda

  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); } 

e para Integer basta alterar o método do chamador e 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(); } 

exemplo 1: GetAllPermutations (“abc”, 3); “abc” “acb” “bac” “bca” “táxi” “cba”

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

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

Aqui está uma solução simples em c # usando recursion,

 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))); } } } 

Aqui está a function que irá imprimir toda a permutação. Esta function implementa a 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(); } 

O abaixo é minha implementação de permutação. Não se importe com os nomes das variables, como eu estava fazendo isso por diversão 🙂

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

Aqui está um exemplo de alto nível que eu escrevi, que ilustra a explicação da linguagem humana que Peter deu:

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

Se o desempenho e a memory forem um problema, sugiro essa implementação muito eficiente. De acordo com o algoritmo de Heap na Wikipedia , ele deve ser o mais rápido. Espero que caiba sua necessidade :-)!

Apenas como comparação disso com uma implementação de Linq para 10! (código incluso):

  • Isto: 36288000 itens em 235 millisecs
  • Linq: 36288000 itens em 50051 millisecs

     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"); } } } 

Aqui está minha solução em JavaScript (NodeJS). A ideia principal é pegar um elemento por vez, “remover” da string, variar o resto dos caracteres e inserir o elemento na 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; 

E aqui estão os testes:

 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); }) }) }) 

Aqui está a solução mais simples que eu posso imaginar:

 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 

A function distribute recebe um novo elemento e uma lista n element e retorna uma lista de n+1 listas, cada uma delas e inserida em um local diferente. Por exemplo, inserindo 10 em cada um dos quatro lugares possíveis na 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]] 

A function de permute dobra sobre cada elemento por sua vez distribuindo sobre as permutações acumuladas até agora, culminando em todas as permutações. Por exemplo, as 6 permutações da 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]] 

Alterar a fold para uma scan para manter os acumuladores intermediários lança alguma luz sobre como as permutações são geradas um elemento por 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]]] 

Lista as permutações de uma string. Evita a duplicação quando os caracteres são repetidos:

 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]); } } } 

Aqui está a function que imprimirá todas as permutações 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; } 

Aqui está uma resposta C # que é um pouco 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; } 

Saída:

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

Esta é a minha solução que é fácil para mim 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 }); } 

Aqui está mais uma implementação do algoritmo 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); } }