JOIN
 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 | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Permutations of an Array << PREV    [ 1 2 ]
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply I think the discussion should have more emphasis in the best practice of using this kind of tool; Just like it is mentioned and used in the MatrixGame & TheLuckyString problems, we need to generate certain rules/filters to optimize the search. To look for all n! possibilities probably never will be a feasible solution. This is also called Combinatorial Explosion which verbatim refers to a growth almost impossible to sustain for the time of this type of TC problems.So more important than the implementation ( which is assumed know -next_permutation()- that this is called Algorithm L in Knuth's TAOCP 4: 7.2.1.2) it is the good use some criteria for pruning combinations (permutations) and at the end we obtain a reasonable running time.Many problems use this kind of booby-trap to let the programmer to try to solve with a plenty quick solution which runs over all permutations (or combinations) that finish with a timeout or an unnecessary overhead as resources used (such us memory).
 Re: Iterating Over All Permutations of an Array (response to post by devwebcl) | Reply That's right and that's because I mention that this algorithm fits only for small values of n. But, first, the recipe is named as it is named, and going to be the one for beginners; second, I don't know any general method of making cutting off in iterating over combinatorial objects - it's should be individual for every such problem; and third, problems where we need to do this are relatively rare in SRMs.
 Re: Iterating Over All Permutations of an Array (response to post by devwebcl) | Reply I don't think this recipe needs this. There are SRM problems which need just what the recipe says - iterating over all permutations. More advanced techniques are not universal, and we'll have recipes about them (namely "Constructing Combinatorial Objects" and "Finding the lexicographically K-th combinatorial object"), but this recipe is hardly a place for them.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply 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 NKolotey) | Reply Thanks for the notice, I really forgot to mention the simplest algorithm for generating permutations. I've added it in the Discussion part of the recipe.
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Permutations of an Array Previous Thread  |  Next Thread << PREV    [ 1 2 ]