列出string/整数的所有排列

编程采访中的一个常见任务(不是从我的访谈经验来看)是采取一个string或一个整数,并列出每一个可能的排列。

有没有这样做的例子和解决这个问题的逻辑?

我已经看到了一些代码片段,但他们没有很好的评论/解释,因此很难遵循。

首先:它当然闻起来像recursion

既然你也想知道这个原理,我就尽力把它解释成人的语言。 我认为在大多数情况下,recursion是非常容易的。 你只需要掌握两个步骤:

  1. 第一步
  2. 所有其他的步骤(所有的都是相同的逻辑)

人类语言

简而言之:
1元素的排列是一个元素。
2.一组元素的排列是每个元素的列表,与其他元素的每一个排列连接在一起。

例:

如果集合只有一个元素 – >
把它返还。
烫发(a) – > a

如果集合有两个字符:对于其中的每个元素:返回元素,添加其余元素的排列,如下所示:

烫发(ab) – >

a + perm(b) – > ab

b + perm(a) – > ba

进一步:对于集合中的每个字符:返回一个字符,并与该集合的其余部分进行连贯

烫发(abc) – >

a + perm(bc) – > abcacb

b + perm(ac) – > bacbca

c + perm(ab) – > cabcba

perm(abc … z) – >

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

我在http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/上find了;伪代码

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#

好的,还有一些更详细的内容(因为它被标记为C#),来自http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html :相当长,但我决定复制它无论如何,这样的post是不依赖于原来的。

该函数接收一串字符,并记下该string的每个可能的排列,例如,如果“ABC”已经被提供,则应该溢出:

ABC,ACB,BAC,BCA,CAB,CBA。

码:

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

如果LINQ被允许使用,那只是两行代码。 请在这里看到我的答案。

编辑

这是我的通用函数,它可以返回T列表中的所有排列(不是组合)

 static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> 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 })); } 

例:

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

输出 – 整数列表的列表:

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

由于这个函数使用LINQ,因此需要.net 3.5或更高版本。

在这里我find了解决办法。 它是用Java编写的,但是我把它转换成了C#。 我希望这会帮助你。

在这里输入图像说明

以下是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; } 

recursion是没有必要的, 这里是关于这个解决scheme的好信息。

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

我已经使用了这个algorithm多年,它有O(N) 时间空间的复杂度来计算每个排列

 public static class SomeExtensions { public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> 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<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> 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<long> 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<T>(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]); } } 

您可以编写交换function来交换字符。
这被称为permute(string,0);

首先,集合有排列,而不是string或整数,所以我只假定你的意思是“string中的字符集”。

请注意,一组大小n有n! 正排列。

以下伪代码(来自维基百科),调用k = 1 … n! 会给所有的排列:

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

下面是等效的Python代码(对于基于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 

在C#中稍微修改版本,在任何types的数组中产生所需的排列。

  // 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<T[]> Permutations<T>(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>(T[] values, int pos1, int pos2) { if (pos1 != pos2) { T tmp = values[pos1]; values[pos1] = values[pos2]; values[pos2] = tmp; } } 

这里有一篇关于查找所有排列的三种algorithm的好文章,其中包括find下一个排列。

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

C ++和Python分别内置了next_permutation和itertools.permutations函数。

这是一个纯粹的functionF#实现:

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 } 

通过改变交换来利用CLR数组的可变性,可以大大提高性能,但是这个实现对于源数组来说是线程安全的,在某些情况下这可能是可取的。 此外,对于具有多于16个元素的数组,必须用具有更高/任意精度的typesreplaceint,因为17因此导致int32溢出。

我很喜欢FBryant87的方法,因为它很简单。 不幸的是,它像许多其他“解决scheme”不提供所有的排列或如果一个整数包含相同的数字不止一次的整数。 以656123为例。 该行:

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

使用Except将导致所有的事件被删除,即当c = 6时,两位数字被删除,我们留下例如5123。由于我试图解决这个问题的解决scheme,我决定尝试自己解决FBryant87的代码作为基础。 这就是我想到的:

 private static List<string> FindPermutations(string set) { var output = new List<string>(); 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; } 

我只是简单地使用.Remove和.IndexOf删除第一个发现的事件。 似乎至less为我的使用目的工作。 我相信它可以变得更聪明。

需要注意的一件事:结果列表可能包含重复项,所以请确保您要么使方法返回例如HashSet,要么使用任何您喜欢的方法返回后删除重复项。

这里是打印所有的permutaion的函数。 这个函数实现了逻辑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(); } 

下面是我的排列实现。 不要介意variables名称,因为我正在这样做的乐趣:)

 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<string> 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<string> comb(string test) { List<string> sec = new List<string>(); List<string> first = new List<string>(); 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<string> 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<string> generateWords(string test) { List<string> final = new List<string>(); 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; } } 

下面是我写的一个高层次的例子,说明了彼得给人的语言解释:

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

这是一个容易理解的permutaion函数为string和整数作为input。 有了这个, 你甚至可以设置你的输出长度 (在正常情况下它等于input长度)

  static ICollection<string> result; public static ICollection<string> GetAllPermutations(string str, int outputLength) { result = new List<string>(); 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<char>(); tempList.RemoveAt(i); MakePermutations(tempList.ToArray(), string.Concat(permutation, possibleArray[i]), outputLength); } } else if (!result.Contains(permutation)) result.Add(permutation); } 

Integer只是改变调用方法和MakePermutations()保持不变:

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

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

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

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

这里是一个在c#中使用recursion的简单解决scheme,

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

这是我的JavaScript解决scheme(NodeJS)。 主要思想是,我们一次只取一个元素,将其从string中“删除”,改变其余字符,并将元素插入到前面。

 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; 

这里是testing:

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

这是我能想到的最简单的解决scheme:

 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 

distribute函数接受一个新元素e和一个n元素列表,并返回一个n+1列表,每个列表在不同的地方插入。 例如,在列表[1;2;3]的四个可能位置中的每一个处插入10

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

permute函数依次permute在每个元素上,依次分布在迄今为止所积累的排列上,最终形成所有排列。 例如,列表[1;2;3]的6个排列:

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

为了让中间的累加器一次一个元素的排列是如何生成的,

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

这是recursion地打印所有排列的函数。

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

这是一个简单的C#答案。

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

输出:

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

这是我的解决scheme,我很容易理解

 class ClassicPermutationProblem { ClassicPermutationProblem() { } private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position) { foreach (T element in list) { List<T> 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<List<int>> GetPermutations(List<int> list) { List<List<int>> results = new List<List<int>>(); PopulatePosition(results, list, new List<int>(), 1); return results; } } static void Main(string[] args) { List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 }); } 

如果性能和内存是一个问题,我build议这个非常有效的实现。 根据维基百科的Heapalgorithm ,它应该是最快的。 希望它会适合您的需要:-)!

就像这个和Linq实现10的比较! (包括代码):

  • 这:235毫秒36288000项
  • Linq:在50051毫升的36288000项

     using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Runtime.CompilerServices; using System.Text; namespace WpfPermutations { /// <summary> /// 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 /// </summary> public static class Permutations { /// <summary> /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. /// </summary> /// <param name="items">Items to permute in each possible ways</param> /// <param name="funcExecuteAndTellIfShouldStop"></param> /// <returns>Return true if cancelled</returns> public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> 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; } /// <summary> /// This function is to show a linq way but is far less efficient /// </summary> /// <typeparam name="T"></typeparam> /// <param name="list"></param> /// <param name="length"></param> /// <returns></returns> static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> 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 })); } /// <summary> /// Swap 2 elements of same type /// </summary> /// <typeparam name="T"></typeparam> /// <param name="a"></param> /// <param name="b"></param> [MethodImpl(MethodImplOptions.AggressiveInlining)] static void Swap<T>(ref T a, ref T b) { T temp = a; a = b; b = temp; } /// <summary> /// Func to show how to call. It does a little test for an array of 4 items. /// </summary> 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"); } } } 

这里还有一个提到的algorithm的实现。

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

列出一个string的排列。 字符重复时避免重复:

 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 Permutation { public static List<string> Permutate(string seed, List<string> 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<string> PermuateRecursive(string seed) { List<string> lstStrs = new List<string>(); 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<string> Permutate(string seed) { loopCounter = 0; List<string> strList = new List<string>(); 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); } } 
  /// <summary> /// Print All the Permutations. /// </summary> /// <param name="inputStr">input string</param> /// <param name="strLength">length of the string</param> /// <param name="outputStr">output string</param> 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); } }