JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Re: Iterating Over All Permutations of an Array Revision History (2 edits)
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) My five cents...If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below``` static void sub(int[] counters, char[] word, int p) { if (p == word.Length) Console.WriteLine(word); else   for (int i = 0; i < 26; i++) if (counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); sub(counters, word, p + 1); counters[i]++; } }   public static void generate(string s) { int[] counters = new int[26]; for (int i = 0; i < s.Length; i++) counters[s[i] - 'A']++;   char[] word = new char[s.Length]; sub(counters, word, 0); }   static void Main(string[] args) { generate("HELLO"); } ```Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it to top just to make code more readable, c# users can use IEnumerable yield technique:``` static IEnumerable sub(int[] counters, char[] word, int p) { if (p == word.Length) yield return new string(word); else   for (int i = 0; i < 26; i++) if (counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); foreach (string w in sub(counters, word, p + 1)) yield return w; counters[i]++; } }   public static IEnumerable generate(string s) { int[] counters = new int[26]; for (int i = 0; i < s.Length; i++) counters[s[i] - 'A']++;   char[] word = new char[s.Length]; foreach(string w in sub(counters, word, 0)) yield return w; }   static void Main(string[] args) { foreach(string w in generate("HELLO")) Console.WriteLine(w); } ```
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) My five cents...If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below``` static void sub(int[] counters, char[] word, int p) { if (p == word.Length) Console.WriteLine(word); else   for (int i = 0; i < 26; i++) if (counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); sub(counters, word, p + 1); counters[i]++; } }   public static void generate(string s) { int[] counters = new int[26]; for (int i = 0; i < s.Length; i++) counters[s[i] - 'A']++;   char[] word = new char[s.Length]; sub(counters, word, 0); }   static void Main(string[] args) { generate("HELLO"); } ```Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it into top just to make code more readable, c# users can use IEnumerable yield technique:``` static IEnumerable sub(int[] counters, char[] word, int p) { if (p == word.Length) yield return new string(word); else   for (int i = 0; i < 26; i++) if (counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); foreach (string w in sub(counters, word, p + 1)) yield return w; counters[i]++; } }   public static IEnumerable generate(string s) { int[] counters = new int[26]; for (int i = 0; i < s.Length; i++) counters[s[i] - 'A']++;   char[] word = new char[s.Length]; foreach(string w in sub(counters, word, 0)) yield return w; }   static void Main(string[] args) { foreach(string w in generate("HELLO")) Console.WriteLine(w); } ```
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) My five cents...If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below``` static void sub(int[] counters, char[] word, int p) { if (p == word.Length) Console.WriteLine(word); else   for (int i = 0; i < 26; i++) if (counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); sub(counters, word, p + 1); counters[i]++; } }   public static void generate(string s) { int[] counters = new int[26]; for (int i = 0; i < s.Length; i++) counters[s[i] - 'A']++;   char[] word = new char[s.Length]; sub(counters, word, 0); }   static void Main(string[] args) { generate("HELLO"); } ```Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it into top just to make code more readable, c# users can use IEnumerable yield technique:``` static IEnumerable sub(int[] counters, char[] word, int p) { if (p == word.Length) yield return word; else   for (int i = 0; i < 26; i++) if (counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); foreach (char[] w in sub(counters, word, p + 1)) yield return w; counters[i]++; } }   public static IEnumerable generate(string s) { int[] counters = new int[26]; for (int i = 0; i < s.Length; i++) counters[s[i] - 'A']++;   char[] word = new char[s.Length]; foreach(char[] w in sub(counters, word, 0)) yield return w; }   static void Main(string[] args) { foreach(char[] w in generate("HELLO")) Console.WriteLine(w); } ```