1: namespace Recursion3
2: { 3: /// <summary>
4: /// Question:
5: /// For a given string prints all it's permutations
6: /// Use the following signature: void PrintPermutations(string word) and solve in recursion.
7: /// </summary>
8: class Program
9: { 10: static void Main(string[] args)
11: { 12: string input = string.Empty;
13: while (input != null)
14: { 15: Console.Write("Permutation target: "); 16: input = Console.ReadLine();
17: long expected = Factor(input.Length);
18: if (expected < 0)
19: { 20: //overflow
21: Console.WriteLine("The string is too long! Try again"); 22: continue;
23: }
24:
25: Console.WriteLine("\nExpecting {0} results, To abort press a or A (any other to continue)", expected); 26: if (StringComparer.OrdinalIgnoreCase.Compare("a",Console.ReadLine())==0) 27: continue;
28:
29: //permutate
30: PrintPermutations(input);
31: }
32: }
33:
34: /// <summary>
35: /// Returns a factor of n (n!)
36: /// </summary>
37: /// <param name="n"></param>
38: /// <returns></returns>
39: private static long Factor(long n)
40: { 41: if (n <=1)
42: return 1;
43: return n * Factor(n - 1);
44: }
45:
46: /// <summary>
47: /// Solution using a bootstrap function
48: /// </summary>
49: /// <param name="word"></param>
50: public static void PrintPermutations(string word)
51: { 52: if (string.IsNullOrEmpty(word))
53: return;
54:
55: PrintPermutations(string.Empty, word,0);
56: }
57:
58: /// <summary>
59: /// Bootstraped function
60: /// </summary>
61: /// <param name="variation"></param>
62: /// <param name="word"></param>
63: /// <param name="charIndex"></param>
64: private static void PrintPermutations(string variation, string word, int charIndex)
65: { 66: ////when the word is empty then the variation is complete
67: if (string.IsNullOrEmpty(word))
68: { 69: Console.WriteLine(variation);
70: return;
71: }
72:
73: //detect permutation end
74: if (charIndex >= word.Length)
75: { 76: return;
77: }
78:
79: PrintPermutations(variation, word,charIndex +1); //the first option is not to use the char at charIndex
80: PrintPermutations(variation + word[charIndex].ToString(), RemoveChar(word,charIndex), 0); //the second options is to use the char at charIndex
81: }
82:
83: /// <summary>
84: /// Utility method that removes char at charIndex from word and returns the new word
85: /// </summary>
86: /// <param name="word"></param>
87: /// <param name="charIndex"></param>
88: /// <returns></returns>
89: private static string RemoveChar(string word, int charIndex)
90: { 91: if (word.Length - 1 == charIndex)
92: return word.Substring(0, charIndex);
93:
94: return word.Substring(0, charIndex) + word.Substring(charIndex + 1);
95: }
96: }
97: }